is_strong_pseudoprime incorrect for bases > n #12

Closed
danaj opened this Issue Mar 19, 2013 · 2 comments

Projects

None yet

2 participants

@danaj
Contributor
danaj commented Mar 19, 2013

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
Owner
leto commented Mar 19, 2013

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

@danaj
Contributor
danaj commented Mar 19, 2013

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_strong_pseudoprime -E
'foreach my $p (@{primes(0,1000)}) { do {die "$p $\n" unless
is_strong_pseudoprime($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
.

@leto leto added a commit that closed this issue Mar 24, 2013
@leto Make is_strong_pseudoprime tests pass and change +1/-1 to be consider…
…ed strong pseudoprimes, fixes #12
d730972
@leto leto closed this in d730972 Mar 24, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment