This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.13 in repository libmath-prime-util-perl.
commit de88bbcfe598a7d4ef0344b26068821c37a39e69 Author: Dana Jacobsen <[email protected]> Date: Sun Oct 28 04:23:06 2012 -0700 Use 2 MR bases for more numbers --- Changes | 2 ++ factor.c | 9 ++++++++- lib/Math/Prime/Util.pm | 18 +++++++++++------- 3 files changed, 21 insertions(+), 8 deletions(-) diff --git a/Changes b/Changes index c49d641..b4a1784 100644 --- a/Changes +++ b/Changes @@ -20,6 +20,8 @@ Revision history for Perl extension Math::Prime::Util. - Some fixes and speedups for ranged primes(). + - In the PP code, use 2 MR bases for more numbers when possible. + 0.11 23 July 2012 - Turn off threading tests on Cygwin, as threads on some Cygwin platforms give random panics (my Win7 64-bit works fine, XP 32-bit does not). diff --git a/factor.c b/factor.c index 450da8a..a75d85e 100644 --- a/factor.c +++ b/factor.c @@ -256,10 +256,16 @@ int _XS_miller_rabin(UV n, const UV *bases, int nbases) croak("Base %"UVuf" is invalid for input %"UVuf, a, n); #endif + /* n is a strong pseudoprime to this base if either + * - a^d = 1 mod n + * - a^(d2^r) = -1 mod n for some r: 0 <= r <= s-1 + */ + x = powmod(a, d, n); if ( (x == 1) || (x == (n-1)) ) continue; - for (r = 0; r < s; r++) { + /* cover r = 1 to s-1, r=0 was just done */ + for (r = 1; r < s; r++) { x = sqrmod(x, n); if (x == 1) { return 0; @@ -296,6 +302,7 @@ int _XS_is_prob_prime(UV n) #else #if 1 /* Better basis from: http://miller-rabin.appspot.com/ */ + /* We could go up to 316_349_281 using 2 bases */ if (n < UVCONST(9080191)) { bases[0] = 31; bases[1] = 73; diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 43eba86..940bd2a 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -953,14 +953,18 @@ sub is_prob_prime { } if ($n < 105936894253) { # BPSW seems to be faster after this - # Deterministic set of Miller-Rabin tests. + # Deterministic set of Miller-Rabin tests. If the MR routines can handle + # bases greater than n, then this can be simplified. my @bases; - if ($n < 9080191) { @bases = (31, 73); } - elsif ($n < 4759123141) { @bases = (2, 7, 61); } - elsif ($n < 105936894253) { @bases = (2, 1005905886, 1340600841); } - elsif ($n < 31858317218647) { @bases = (2, 642735, 553174392, 3046413974); } - elsif ($n < 3071837692357849) { @bases = (2, 75088, 642735, 203659041, 3613982119); } - else { @bases = (2, 325, 9375, 28178, 450775, 9780504, 1795265022); } + if ($n < 9080191) { @bases = (31, 73); } + elsif ($n < 19471033) { @bases = ( 2, 299417); } + elsif ($n < 38010307) { @bases = ( 2, 9332593); } + elsif ($n < 316349281) { @bases = ( 11000544, 31481107); } + elsif ($n < 4759123141) { @bases = ( 2, 7, 61); } + elsif ($n < 105936894253) { @bases = ( 2, 1005905886, 1340600841); } + elsif ($n < 31858317218647) { @bases = ( 2, 642735, 553174392, 3046413974); } + elsif ($n < 3071837692357849) { @bases = ( 2, 75088, 642735, 203659041, 3613982119); } + else { @bases = ( 2, 325, 9375, 28178, 450775, 9780504, 1795265022); } return Math::Prime::Util::PP::miller_rabin($n, @bases) ? 2 : 0; } -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git _______________________________________________ Pkg-perl-cvs-commits mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
