is_strong_pseudoprime incorrect for bases > n

[danaj]

is_strong_pseudoprime(367, 1101) returns 0 (1101 = 367*3)

The function needs to either indicate using bases >= n are invalid, or do something like (pseudocode):

if (base >= n) base %= n if (base <= 1 || base == n-1) return 1

The first protects us from mistakes such as indicating primes are composites when the base is a multiple of n. The latter opens up better deterministic tests since it won't return wrong answers.

I'll put a patch on my todo list unless someone gets to it first.

[leto]

Thanks for reporting this, @danaj ! Have you noticed similar behavior in other functions, or just is_strong_pseudoprime ?

[danaj]

It should just affect is_strong_pseudoprime and is_pseudoprime. There isn't a base for Lucas pseudoprimes, and the other functions don't take a base as input.

Miller's paper indicates 1 < a < n. The usual M-R algorithm with a random base indicates selecting one in the range [2, n-2]. My code used to croak if the base was out of range, but I changed both MPU and MPU::GMP to do the modulo so large bases can be used.

I just added these tests to Math::Prime::Util::GMP's test suite:

is( is_strong_pseudoprime( 3, 3), 1, "spsp( 3, 3)"); is( is_strong_pseudoprime( 11, 11), 1, "spsp( 11, 11)"); is( is_strong_pseudoprime( 89, 5785), 1, "spsp( 89, 5785)"); is( is_strong_pseudoprime(257, 6168), 1, "spsp(257, 6168)"); is( is_strong_pseudoprime(367, 367), 1, "spsp(367, 367)"); is( is_strong_pseudoprime(367, 1101), 1, "spsp(367, 1101)"); is( is_strong_pseudoprime(49001, 921211727), 0, "spsp(49001, 921211727)"); is( is_strong_pseudoprime( 331, 921211727), 1, "spsp( 331, 921211727)"); is( is_strong_pseudoprime(49117, 921211727), 1, "spsp(49117, 921211727)");

as well as trying these:

This should not print anything, indicating 921211727 is a deterministic

base

for all n < 49141.

perl -MMath::Primality=is_prime,is_strong_pseudoprime -E 'foreach my $n (2..49139) { warn "$n\n" if is_strong_pseudoprime($n, 921211727) != !!is_prime($n) }'

Verify that no prime 0..1000 will be marked composite regardless of the

base perl -MMath::Prime::Util=primes -MMath::Primality=is_strongpseudoprime -E 'foreach my $p (@{primes(0,1000)}) { do {die "$p $\n" unless is_strongpseudoprime($p,$) } for 2..10000 }'

Both currently fail for Math::Primality (with the caveat that we're giving it bases out of the range it was coded to handle, so we shouldn't be shocked).

On Tue, Mar 19, 2013 at 10:45 AM, leto notifications@github.com wrote:

Thanks for reporting this, @danaj https://github.com/danaj ! Have you noticed similar behavior in other functions, or just is_strong_pseudoprime ?

— Reply to this email directly or view it on GitHubhttps://github.com/leto/math--primality/issues/12#issuecomment-15131105 .