This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.32 in repository libmath-prime-util-perl.
commit 829338fdbea4a056f775a62e4851160706941fc7 Author: Dana Jacobsen <d...@acm.org> Date: Fri Aug 9 18:38:03 2013 -0700 Updates for random_nbit_prime and documentation --- lib/Math/Prime/Util.pm | 132 +++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 122 insertions(+), 10 deletions(-) diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index efce890..4b0a753 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -723,7 +723,7 @@ sub primes { if ($_big_gcd_use < 0) { $_big_gcd_use = 0; my $lib = Math::BigInt->config()->{lib}; - $_big_gcd_use = 1 if $lib =~ /^Math::BigInt::(GMP|Pari)/; + $_big_gcd_use = 1 if !$_HAVE_GMP && $lib =~ /^Math::BigInt::(GMP|Pari)/; _make_big_gcds() if $_big_gcd_use; } @@ -741,7 +741,12 @@ sub primes { next unless (0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1)[$prime]; return $prime; } - # Perform quick trial division + # With GMP, the fastest thing to do is check primality. + if ($_HAVE_GMP) { + next unless Math::Prime::Util::GMP::is_prime($prime); + return $prime; + } + # No MPU:GMP, so primality checking is slow. Skip some composites here. next unless Math::BigInt::bgcd($prime, 7436429) == 1; if ($_big_gcd_use && $prime > $_big_gcd_top) { next unless Math::BigInt::bgcd($prime, $_big_gcd[0]) == 1; @@ -819,6 +824,39 @@ sub primes { my($bits) = @_; _validate_num($bits, 2) || _validate_positive_integer($bits, 2); + # Fouque and Tibouchi (2011) Algorithm 1 (basic) + if (1 && $bits > 64) { + if (!defined $Math::BigInt::VERSION) { + eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } + or do { croak "Cannot load Math::BigInt"; }; + } + my $irandf = _get_rand_func(); + my $l = ($_Config{'maxbits'} > 32 && $bits > 79) ? 63 : 31; + my $arange = (1 << $l) - 1; # 2^$l-1 + my $brange = Math::BigInt->new(2)->bpow($bits-$l-2)->bsub(1); + my $b = 2 * $irandf->($brange) + 1; + # Precalculate some modulii (TODO: add more or use F&T Alg 2) + my $em3 = ($bits % 2) ? (0,1,2)[$b % 3] : (0,2,1)[$b % 3]; + my $loop_limit = 1_000_000; + while ($loop_limit-- > 0) { + my $a = (1 << $l) + $irandf->($arange); + next if $a % 3 == $em3; + my $p = Math::BigInt->new("$a")->blsft($bits-$l-1)->badd($b); + # p: 1aaaaaaaabbbbbbbbbbbbbbbbbbbb1 + #die " $a $b $p" if $a % 3 == $em3 && $p % 3 != 0; + #die "!$a $b $p" if $a % 3 != $em3 && $p % 3 == 0; + if ($_HAVE_GMP) { + next unless Math::Prime::Util::GMP::is_prime($p); + } else { + next unless Math::BigInt::bgcd($p, 4127218095) == 1; + next unless Math::BigInt::bgcd($p, 3948078067) == 1; + next unless is_prob_prime($p); + } + return $p; + } + croak "Random function broken?"; + } + if (!defined $_random_nbit_ranges[$bits]) { my $bigbits = $bits > $_Config{'maxbits'}; croak "Large random primes not supported on old Perl" if $] < 5.008 && $_Config{'maxbits'} > 32 && !$bigbits && $bits > 49; @@ -2457,6 +2495,14 @@ L</is_prime> return probable prime results using the extra-strong Baillie-PSW test, which has had no counterexample found since it was published in 1980. +For cryptographic key generation, you may want even more testing for probable +primes (NIST recommends some additional M-R tests). This can be done using +additional random bases with L</is_strong_pseudoprime>, or a different test +such as L</is_frobenius_underwood_pseudoprime>. Even better, make sure +L<Math::Prime::Util::GMP> is installed and use L</is_provable_prime> which +should be reasonably fast for sizes under 2048 bits. +Another possibility is to use L<Math::Prime::Util/random_maurer_prime> which +constructs a random provable prime. =head2 primes @@ -3407,12 +3453,13 @@ between 2 and the maximum representable bits (32, 64, or 100000 for native set will be uniformly selected, with randomness supplied via calls to the C<irand> function as described above. -Since this uses the random_prime function, all uniformity properties of that -function apply to this. The n-bit range is partitioned into nearly equal -segments less than C<2^32>, a segment is randomly selected, then the trivial -Monte Carlo algorithm is used to select a prime from within the segment. -This gives a reasonably uniform distribution, doesn't use excessive random -source, and can be very fast. +For bit size of 64 and lower, we use L</random_prime>, which will result in +uniform results. For sizes larger than 64, Algorithm 1 of Fouque and Tibouchi +(2011) is used, wherein we select a random odd number for the lower bits, then +loop selecting random upper bits until the result is prime. This gives a very +uniform distribution while running quickly. The C<irand> function is used +for randomness, so all the discussion in L</random_prime> about that applies +here. The result will be a BigInt if the number of bits is greater than the native bit size. For better performance with large bit sizes, install @@ -3470,6 +3517,14 @@ partial result, and constructs a primality certificate for the final result, which is verified. These add additional checks that the resulting value has been properly constructed. +An alternative to this function is to run L</is_provable_prime> on the +result of L</random_nbit_prime>, which will provide more diversity and +will be faster up to 512 or so bits. Maurer's method should be much +faster for large bit sizes (larger than 2048). If you don't need absolutely +proven results, then using L</random_nbit_prime> followed by additional +tests (L</is_strong_pseudoprime> and/or L</is_frobenius_underwood_pseudoprime>) +should be much faster. + =head2 random_maurer_prime_with_cert @@ -4164,6 +4219,8 @@ functions. All with fairly minimal installation requirements. =head1 PERFORMANCE +=head2 PRIME COUNTS + Counting the primes to C<10^10> (10 billion), with time in seconds. Pi(10^10) = 455,052,511. The numbers below are for sieving. Calculating C<Pi(10^10)> takes 0.064 @@ -4213,6 +4270,7 @@ and 25+ GB of RAM. SymPy 0.7.1 C<primepi> takes 292.2s. However there are very fast solutions written by Robert William Hanks (included in the xt/ directory of this distribution): pure Python in 12.1s and NUMPY in 2.8s. +=head2 PRIMALITY TESTING C<is_prime>: my impressions for various sized inputs: @@ -4287,6 +4345,7 @@ it is still much, much slower than a BPSW probable prime test for large inputs. =back +=head2 FACTORING Factoring performance depends on the input, and the algorithm choices used are still being tuned. L<Math::Factor::XS> is very fast when given input with @@ -4318,6 +4377,7 @@ and L<Pari|http://pari.math.u-bordeaux.fr/>. The latest yafu should cover most uses, with GGNFS likely only providing a benefit for numbers large enough to warrant distributed processing. +=head2 PRIMALITY PROVING The C<n-1> proving algorithm in L<Math::Prime::Util::GMP> compares well to the version including in Pari. Both are pretty fast to about 60 digits, and @@ -4329,8 +4389,60 @@ including creating a certificate. Times below 200 digits are faster than Pari 2.3.5's APR-CL proof. For larger inputs the bottleneck is a limited set of discriminants, and time becomes more variable. There is a larger set of discriminants on github that help, with 300-digit primes taking ~5 seconds on -average and typically under a minute for 500-digits. For serious primality -proving, I recommend L<Primo|http://www.ellipsa.eu/>. +average and typically under a minute for 500-digits. For primality proving +with very large numbers, I recommend L<Primo|http://www.ellipsa.eu/>. + +=head2 RANDOM PRIME GENERATION + +Seconds per prime for random prime generation on a circa-2009 workstation, +with L<Math::Prime::Util::GMP> installed. + + bits random +testing random(p) Maurer CPMaurer + ----- -------- -------- --------- -------- -------- + 64 0.0003 +0.000003 0.0003 0.0003 0.022 + 128 0.0040 +0.00016 0.0099 0.081 0.057 + 256 0.0073 +0.0004 0.057 0.19 0.16 + 512 0.020 +0.0012 0.43 0.52 0.41 + 1024 0.089 +0.0060 6.3 1.3 2.19 + 2048 0.62 +0.039 4.8 10.99 + 4096 6.24 +0.25 31.9 79.71 + 8192 58.6 +1.61 234.0 947.3 + + random = random_nbit_prime (results pass BPSW) + random+ = additional time for 3 M-R and a frobenius test + random(p) = is_provable_prime(random_nbit_prime(bits)) + maurer = random_maurer_prime + CPMaurer = Crypt::Primes::maurer + +L</random_nbit_prime> is reasonably fast, and for most purposes should be +adequate. For cryptographic purposes, one may want additional tests or a +proven prime. Additional tests are quite cheap, as shown by the time for +three extra M-R and a Frobenius test. At these bit sizes, the chances a +composite number passes BPSW, three more M-R tests, and a Frobenius test +is I<extraordinarily> small. + +For bit sizes under 600 or so (200 digits), using L</is_provable_prime> on +the result of L</random_nbit_prime> is quite fast. Typically this will +actually be faster than generating a proven prime with Maurer's algorithm. +However, as the bit sizes increase, proving primality becomes quite expensive +so Maurer's method is typically best for proven random primes over 512 bits. + +L</random_maurer_prime> constructs a provable prime. A primality test is +run on each intermediate, and it also constructs a complete primality +certificate which is verified at the end (and can be returned). While the +result is uniformly distributed, only about 10% of the primes in the range +are selected for output. This is a result of the FastPrime algorithm and +is usually unimportant. + +L<Crypt::Primes/maurer> is included for comparison. It is pretty fast for +small sizes but gets slow as the size increases. It does not perform any +primality checks on the intermediate results or the final result (I highly +recommended you run a primality test on the output). +Additionally important for servers, L<Crypt::Primes/maurer> uses excessive +system entropy and can grind to a halt if C</dev/random> is exhausted +(it can take B<days> to return). The times above are on a machine running +L<HAVEGED|http://www.issihosts.com/haveged/> +so never waits for entropy. =head1 AUTHORS -- 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