This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.19
in repository libmath-prime-util-perl.

commit a522f78d3d165f3ea13b3c50779085c48027bca9
Author: Dana Jacobsen <d...@acm.org>
Date:   Mon Jan 14 02:28:19 2013 -0800

    Add random_strong_prime, update to 0.18
---
 Changes                | 11 +++++++
 Makefile.PL            |  8 +++--
 README                 |  2 +-
 TODO                   |  3 ++
 lib/Math/Prime/Util.pm | 79 +++++++++++++++++++++++++++++++++++++++++++++++---
 t/81-bignum.t          |  8 ++++-
 6 files changed, 102 insertions(+), 9 deletions(-)

diff --git a/Changes b/Changes
index 5f361fa..ff596b5 100644
--- a/Changes
+++ b/Changes
@@ -1,5 +1,16 @@
 Revision history for Perl extension Math::Prime::Util.
 
+0.18  14 January 2012
+
+    - Add random_strong_prime.
+
+    - Fix builds with Solaris 9 and older.
+
+    - Add some debug info to perhaps find out why old ActiveState Perls are
+      dying in Math::BigInt::Calc, as if they were using really old versions
+      that run out of memory trying to calculate '2 ** 66'.
+      http://code.activestate.com/ppm/Math-Prime-Util/
+
 0.17  20 December 2012
 
     - Perl 5.8.1 - 5.8.7 miscalculates 12345 ** 4, which I used in a test.
diff --git a/Makefile.PL b/Makefile.PL
index 27629f9..a89dd6a 100644
--- a/Makefile.PL
+++ b/Makefile.PL
@@ -33,9 +33,11 @@ WriteMakefile1(
                       'Math::BigFloat'   => '1.59',
                     },
     META_MERGE   => {
-                      recommends => { 'Math::Prime::Util::GMP' => 0.06, },
-                      recommends => { 'Math::BigInt::GMP' => 0, },
-                      recommends => { 'Math::MPFR' => 0, },
+                      recommends => {
+                        'Math::Prime::Util::GMP' => 0.06,
+                        'Math::BigInt::GMP'      => 0,
+                        'Math::MPFR'             => 2.03,
+                      },
                     },
 
     MIN_PERL_VERSION => 5.006002,
diff --git a/README b/README
index be92e29..efb7df9 100644
--- a/README
+++ b/README
@@ -1,4 +1,4 @@
-Math::Prime::Util version 0.17
+Math::Prime::Util version 0.18
 
 A set of utilities related to prime numbers.  These include multiple sieving
 methods, is_prime, prime_count, nth_prime, approximations and bounds for
diff --git a/TODO b/TODO
index 55b7ef0..e6c364e 100644
--- a/TODO
+++ b/TODO
@@ -45,3 +45,6 @@
   tinymt32, seed it using the system rand (multiple calls, just use 8-bits
   each), then use it to get 32-bit irands.  This would only be used if they
   didn't give us a RNG (so they don't care about strict crypto).
+
+- Perfect power from Dietzfelbinger algorithm 2.3.5 works a bit better.
+  Newton's method would be even better.
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 7156271..ad82c3f 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -5,7 +5,7 @@ use Carp qw/croak confess carp/;
 
 BEGIN {
   $Math::Prime::Util::AUTHORITY = 'cpan:DANAJ';
-  $Math::Prime::Util::VERSION = '0.17';
+  $Math::Prime::Util::VERSION = '0.18';
 }
 
 # parent is cleaner, and in the Perl 5.10.1 / 5.12.0 core, but not earlier.
@@ -22,7 +22,8 @@ our @EXPORT_OK = qw(
                      next_prime  prev_prime
                      prime_count prime_count_lower prime_count_upper 
prime_count_approx
                      nth_prime nth_prime_lower nth_prime_upper nth_prime_approx
-                     random_prime random_ndigit_prime random_nbit_prime 
random_maurer_prime
+                     random_prime random_ndigit_prime random_nbit_prime
+                     random_strong_prime random_maurer_prime
                      primorial pn_primorial
                      factor all_factors
                      moebius euler_phi jordan_totient
@@ -788,7 +789,7 @@ sub primes {
     _validate_positive_integer($bits, 2);
 
     if (!defined $_random_nbit_ranges[$bits]) {
-      my $bigbits = $bits > $_Config{'maxbits'};
+      my $bigbits = $bits > $_Config{'maxbits'}; # || ($] < 5.8 && $bits > 49);
       if ($bigbits) {
         if (!defined $Math::BigInt::VERSION) {
           eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 
1; }
@@ -821,6 +822,7 @@ sub primes {
     # could go even higher if we used is_provable_prime or looked for is_prime
     # returning 2.  This should be reasonably fast to ~128 bits with MPU::GMP.
     my $p0 = $_Config{'maxbits'};
+    $p0 = 32 if $] < 5.8 && $p0 > 32;
 
     return random_nbit_prime($k) if $k <= $p0;
 
@@ -938,6 +940,45 @@ sub primes {
     croak "Failure in random_maurer_prime, could not find a prime\n";
   } # End of random_maurer_prime
 
+  # Gordon's algorithm for generating a strong prime.
+  sub random_strong_prime {
+    my($t) = @_;
+    _validate_positive_integer($t, 128);
+
+    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   = (($t+1) >> 1) - 2;
+    my $lp  = int($t/2) - 20;
+    my $lpp = $l - 20;
+    while (1) {
+      my $qp  = random_nbit_prime($lp);
+      my $qpp = random_nbit_prime($lpp);
+      $qp  = Math::BigInt->new("$qp")  unless ref($qp)  eq 'Math::BigInt';
+      $qpp = Math::BigInt->new("$qpp") unless ref($qpp) eq 'Math::BigInt';
+      my ($il, $rem) = Math::BigInt->new(2)->bpow($l-1)->bsub(1)->bdiv(2*$qpp);
+      $il++ if $rem > 0;
+      my $iu = Math::BigInt->new(2)->bpow($l)->bsub(2)->bdiv(2*$qpp);
+      my $istart = $il + $irandf->($iu - $il);
+      for (my $i = $istart; $i <= $iu; $i++) {  # Search for q
+        my $q = 2 * $i * $qpp + 1;
+        next unless is_prob_prime($q);
+        my $pp = $qp->copy->bmodpow($q-2, $q)->bmul(2)->bmul($qp)->bsub(1);
+        my ($jl, $rem) = 
Math::BigInt->new(2)->bpow($t-1)->bsub($pp)->bdiv(2*$q*$qp);
+        $jl++ if $rem > 0;
+        my $ju = 
Math::BigInt->new(2)->bpow($t)->bsub(1)->bsub($pp)->bdiv(2*$q*$qp);
+        my $jstart = $jl + $irandf->($ju - $jl);
+        for (my $j = $jstart; $j <= $ju; $j++) {  # Search for p
+          my $p = $pp + 2 * $j * $q * $qp;
+          return $p if is_prob_prime($p);
+        }
+      }
+    }
+  }
+
 } # end of the random prime section
 
 sub primorial {
@@ -1744,7 +1785,7 @@ Math::Prime::Util - Utilities related to prime numbers, 
including fast sieves an
 
 =head1 VERSION
 
-Version 0.17
+Version 0.18
 
 
 =head1 SYNOPSIS
@@ -1847,6 +1888,7 @@ Version 0.17
   my $rand_prime = random_prime(100, 10000); # random prime within a range
   my $rand_prime = random_ndigit_prime(6);   # random 6-digit prime
   my $rand_prime = random_nbit_prime(128);   # random 128-bit prime
+  my $rand_prime = random_strong_prime(256); # random 256-bit strong prime
   my $rand_prime = random_maurer_prime(256); # random 256-bit provable prime
 
 
@@ -2442,6 +2484,35 @@ bit size.  For better performance with very large bit 
sizes, install
 L<Math::BigInt::GMP>.
 
 
+=head2 random_strong_prime
+
+  my $bigprime = random_strong_prime(512);
+
+Constructs an n-bit strong prime using Gordon's algorithm.  We consider a
+strong prime I<p> to be one where
+
+=over
+
+=item * I<p> is large.   This function uses 128 as a minimum.
+
+=item * I<p-1> has a large prime factor I<r>.
+
+=item * I<p+1> has a large prime factor I<s>
+
+=item * I<r-1> has a large prime factor I<t>
+
+=back
+
+Using a strong prime in cryptography guards against easy factoring with
+algorithms like Pollard's Rho.  Rivest and Silverman (1999) present a case
+that using strong primes is unnecessary, and most modern cryptographic systems
+agree.  First, the smoothness does not affect more modern factoring methods
+such as ECM.  Second, modern factoring methods like GNFS are far faster than
+either method so make the point moot.  Third, due to key size growth and
+advances in factoring and attacks, for practical purposes, using large random
+primes offer security equivalent to using strong primes.
+
+
 =head2 random_maurer_prime
 
   my $bigprime = random_maurer_prime(512);
diff --git a/t/81-bignum.t b/t/81-bignum.t
index f8fe390..7fcc956 100644
--- a/t/81-bignum.t
+++ b/t/81-bignum.t
@@ -69,7 +69,7 @@ plan tests =>  0
              + scalar(keys %factors)
              + scalar(keys %allfactors)
              + 2   # moebius, euler_phi
-             + 12  # random primes
+             + 15  # random primes
              + 0;
 
 # Using GMP makes these tests run about 2x faster on some machines
@@ -102,6 +102,7 @@ use Math::Prime::Util qw/
   random_prime
   random_ndigit_prime
   random_nbit_prime
+  random_strong_prime
   random_maurer_prime
 /;
 # TODO:  is_strong_lucas_pseudoprime
@@ -208,6 +209,11 @@ cmp_ok( $randprime, '>', 2**79, "random 80-bit prime isn't 
too small");
 cmp_ok( $randprime, '<', 2**80, "random 80-bit prime isn't too big");
 ok( is_prime($randprime), "random 80-bit prime is prime");
 
+$randprime = random_strong_prime(256);
+cmp_ok( $randprime, '>', 2**255, "random 256-bit strong prime isn't too 
small");
+cmp_ok( $randprime, '<', 2**256, "random 256-bit strong prime isn't too big");
+ok( is_prime($randprime), "random 80-bit strong prime is prime");
+
 SKIP: {
   skip "Your 64-bit Perl is broken, skipping maurer prime", 3 if $broken64;
   $randprime = random_maurer_prime(80);

-- 
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

Reply via email to