is_pseudoprime_small_power has bugs with get_data=True

[itolkov]

sage: is_pseudoprime_small_power(31^2, get_data=True)
[(31, 2)]
sage: is_pseudoprime_small_power(31, get_data=True)
True

Also, code can be written much better.

Apply: trac_11430_pseudoprime.patch​

[itolkov]

Timing (ispsp is a more compact version, ispsp2 is this version, is_pseudoprime_small_power is the current version):

sage: timeit('ispsp(3^1024, bound=1024)')
sage: timeit('ispsp2(3^1024, bound=1024)')
sage: timeit('is_pseudoprime_small_power(3^1024, bound=1024)')
125 loops, best of 3: 3.29 ms per loop
125 loops, best of 3: 3.29 ms per loop
125 loops, best of 3: 3.29 ms per loop

sage: timeit('ispsp(31, bound=1024)')
sage: timeit('ispsp2(31, bound=1024)')
sage: timeit('is_pseudoprime_small_power(31, bound=1024)')
625 loops, best of 3: 3.45 µs per loop
625 loops, best of 3: 1.8 µs per loop
625 loops, best of 3: 1.47 µs per loop

sage: timeit('ispsp(31^2, bound=1024)')
sage: timeit('ispsp2(31^2, bound=1024)')
sage: timeit('is_pseudoprime_small_power(31^2, bound=1024)')
625 loops, best of 3: 6.41 µs per loop
625 loops, best of 3: 5.92 µs per loop
625 loops, best of 3: 15.1 µs per loop

sage: timeit('ispsp(31^5, bound=1024)')
sage: timeit('ispsp2(31^5, bound=1024)')
sage: timeit('is_pseudoprime_small_power(31^5, bound=1024)')
625 loops, best of 3: 9.45 µs per loop
625 loops, best of 3: 8.92 µs per loop
625 loops, best of 3: 22 µs per loop

[mariah]

Needs a proper commit message. See http://www.sagemath.org/doc/developer/walk_through.html#submitting-a-change.

[itolkov]

Updated with commit message, do not use 11430-arith.patch

[itolkov]

Got it. Done.

[mariah]

I applied the patch to sage-4.7.1.alpha2, did 'sage -b', and verified that the patch fixed the reported problem. I then did 'make testlong'. All tests passed. Positive review!