This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.10 in repository libmath-prime-util-perl.
commit 0c0f9107c175010ed902190f9b81b4b7eac937f0 Author: Dana Jacobsen <d...@acm.org> Date: Tue Jul 3 11:07:11 2012 -0600 Miller Rabin returns 0 or 1 only. Export strong Lucas pseudoprime function --- XS.xs | 2 +- examples/bench-isprime-bpsw.pl | 26 ++++++++++++++++++++++++++ lib/Math/Prime/Util.pm | 24 +++++++++++++++++++++--- lib/Math/Prime/Util/PP.pm | 2 +- 4 files changed, 49 insertions(+), 5 deletions(-) diff --git a/XS.xs b/XS.xs index 1e8ecfa..1452388 100644 --- a/XS.xs +++ b/XS.xs @@ -351,7 +351,7 @@ miller_rabin(IN UV n, ...) if (items < 2) croak("No bases given to miller_rabin"); if ( (n == 0) || (n == 1) ) XSRETURN_IV(0); /* 0 and 1 are composite */ - if ( (n == 2) || (n == 3) ) XSRETURN_IV(2); /* 2 and 3 are prime */ + if ( (n == 2) || (n == 3) ) XSRETURN_IV(1); /* 2 and 3 are prime */ if (( n % 2 ) == 0) XSRETURN_IV(0); /* MR works with odd n */ while (c < items) { int b = 0; diff --git a/examples/bench-isprime-bpsw.pl b/examples/bench-isprime-bpsw.pl new file mode 100755 index 0000000..86c00f6 --- /dev/null +++ b/examples/bench-isprime-bpsw.pl @@ -0,0 +1,26 @@ +#!/usr/bin/env perl +use strict; +use warnings; +$| = 1; # fast pipes + +use Math::Prime::Util; +use Math::Primality; + +srand(500); +use bigint try=>'GMP'; +use Math::BigInt::Random::OO; +#my $gen = Math::BigInt::Random::OO -> new(length => 50); +my $gen = Math::BigInt::Random::OO -> new(length => 25); + +my @rns; +push @rns, $gen->generate() for (1 .. 100); + +use Benchmark qw/:all/; +cmpthese(-.5, { + "MP MR" => sub { Math::Primality::is_strong_pseudoprime("$_","2") for @rns; }, + "MPU MR" => sub { Math::Prime::Util::PP::miller_rabin($_,2) for @rns; }, + "MP LP" => sub { Math::Primality::is_strong_lucas_pseudoprime("$_") for @rns;}, + "MPU LP" => sub { Math::Prime::Util::PP::is_strong_lucas_pseudoprime($_) for @rns;}, + "MP IP" => sub { Math::Primality::is_prime("$_") for @rns;}, + "MPU IP" => sub { Math::Prime::Util::PP::is_prime($_) for @rns;}, +}); diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 706f559..edc3cf7 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -14,7 +14,7 @@ use base qw( Exporter ); our @EXPORT_OK = qw( prime_get_config prime_precalc prime_memfree - is_prime is_prob_prime miller_rabin + is_prime is_prob_prime miller_rabin is_strong_lucas_pseudoprime primes next_prime prev_prime prime_count prime_count_lower prime_count_upper prime_count_approx @@ -482,6 +482,10 @@ sub is_prob_prime { return ($n <= 18446744073709551615) ? 2 : 1; } +sub is_strong_lucas_pseudoprime { + return Math::Prime::Util::PP::is_strong_lucas_pseudoprime(@_); +} + ############################################################################# sub prime_count_approx { @@ -865,8 +869,13 @@ than L<Math::Pari> for 64-bit operations, with the exception of factoring certain 16-20 digit numbers. The main development of the module has been for working with Perl UVs, so -32-bit or 64-bit. Bignum support is limited. If you need full bignum -support for these types of functions inside Perl now, I recommend L<Math::Pari>. +32-bit or 64-bit. Bignum support is limited. On advantage is that it requires +no external software (e.g. GMP or Pari). If you need full bignum support for +these types of functions inside Perl now, I recommend L<Math::Pari>. +While this module contains all the functionality of L<Math::Primality>, and is +far faster on 64-bit input, bigint performance varies. On my 64-bit machine, +L<Math::Primality> works well and is quite a bit faster than this module. On +my 32-bit machine, L<Math::Primality> is very slow and consumes a lot of memory. The module is thread-safe and allows concurrency between Perl threads while still sharing a prime cache. It is not itself multithreaded. See the @@ -880,6 +889,7 @@ A number of the functions support big numbers, but currently not all. The ones that do: is_prob_prime + is_strong_lucas_pseudoprime prime_count_lower prime_count_upper prime_count_approx @@ -1093,6 +1103,14 @@ other implementations including L<Math::Primality>'s C<is_strong_pseudoprime> function. +=head2 is_strong_lucas_pseudoprime + +Takes a positive number as input, and returns 1 if the input is a strong +Lucas pseudoprime using the Selfridge method of choosing D, P, and Q (hence +some sources call this a strong Lucas-Selfridge pseudoprime). This is one +half of the BPSW primality test (the Miller-Rabin test being the other). + + =head2 is_prob_prime my $prob_prime = is_prob_prime($n); diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index e72ebc7..bb1b98a 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -529,7 +529,7 @@ sub miller_rabin { croak "No bases given to miller_rabin" unless @bases; return 0 if ($n == 0) || ($n == 1); - return 2 if ($n == 2) || ($n == 3); + return 1 if ($n == 2) || ($n == 3); return 0 if ($n % 2) == 0; # I was using bignum here for a while, but doing "$a ** $d" with a -- 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 Pkg-perl-cvs-commits@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits