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

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

commit 67508d1b9c2446ae1aa6a03b66224c5158526877
Author: Dana Jacobsen <d...@acm.org>
Date:   Thu Mar 6 12:16:25 2014 -0800

    Shawe-Taylor random proven primes from FIPS 186-4
---
 Changes                             |  7 ++++
 Makefile.PL                         |  1 +
 TODO                                |  2 --
 lib/Math/Prime/Util.pm              | 58 ++++++++++++++++++++++++++----
 lib/Math/Prime/Util/RandomPrimes.pm | 70 +++++++++++++++++++++++++++++--------
 t/16-randomprime.t                  | 17 +++++++--
 6 files changed, 129 insertions(+), 26 deletions(-)

diff --git a/Changes b/Changes
index 5be7e68..7c79f09 100644
--- a/Changes
+++ b/Changes
@@ -2,6 +2,13 @@ Revision history for Perl module Math::Prime::Util
 
 0.40  2014-03
 
+    [ADDED]
+
+    - random_shawe_taylor_prime              FIPS 186-4 random proven prime
+    - random_shawe_taylor_prime_with_cert    as above with certificate
+
+    [FUNCTIONALITY AND PERFORMANCE]
+
     - Update PP Frobenius-Underwood test.
 
     - Speed up exp_mangoldt.
diff --git a/Makefile.PL b/Makefile.PL
index f0ddf69..104d094 100644
--- a/Makefile.PL
+++ b/Makefile.PL
@@ -70,6 +70,7 @@ WriteMakefile1(
                      'Math::Prime::Util::GMP' => 0.16,
                      'Math::BigInt::GMP'      => 0,
                      'Math::MPFR'             => 2.03,
+                     'Digest::SHA'            => 4.00,
                    },
                  },
                  test  => {
diff --git a/TODO b/TODO
index 2839e67..021d8b0 100644
--- a/TODO
+++ b/TODO
@@ -68,5 +68,3 @@
 - Ensure a fast path for Math::GMP from MPU -> MPU:GMP -> GMP, and back.
 
 - znlog better implementation
-
-- Add Shawe-Taylor random primes, from FIPS-186-4.
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 7f5aba5..d9cca63 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -36,7 +36,7 @@ our @EXPORT_OK =
       random_prime random_ndigit_prime random_nbit_prime random_strong_prime
       random_proven_prime random_proven_prime_with_cert
       random_maurer_prime random_maurer_prime_with_cert
-      random_shawe_taylor_prime
+      random_shawe_taylor_prime random_shawe_taylor_prime_with_cert
       primorial pn_primorial consecutive_integer_lcm
       gcd lcm factor factor_exp all_factors divisors
       moebius mertens euler_phi jordan_totient exp_mangoldt liouville
@@ -336,18 +336,26 @@ sub random_maurer_prime {
   return Math::Prime::Util::RandomPrimes::random_maurer_prime($bits);
 }
 
+sub random_maurer_prime_with_cert {
+  my($bits) = @_;
+  _validate_num($bits, 2) || _validate_positive_integer($bits, 2);
+  require Math::Prime::Util::RandomPrimes;
+  return Math::Prime::Util::RandomPrimes::random_maurer_prime_with_cert($bits);
+}
+
 sub random_shawe_taylor_prime {
   my($bits) = @_;
   _validate_num($bits, 2) || _validate_positive_integer($bits, 2);
   require Math::Prime::Util::RandomPrimes;
-  return Math::Prime::Util::RandomPrimes::random_shawe_taylor_prime(@_);
+  my ($n, $cert) = 
Math::Prime::Util::RandomPrimes::random_shawe_taylor_prime_with_cert($bits);
+  return $n;
 }
 
-sub random_maurer_prime_with_cert {
+sub random_shawe_taylor_prime_with_cert {
   my($bits) = @_;
   _validate_num($bits, 2) || _validate_positive_integer($bits, 2);
   require Math::Prime::Util::RandomPrimes;
-  return Math::Prime::Util::RandomPrimes::random_maurer_prime_with_cert($bits);
+  return 
Math::Prime::Util::RandomPrimes::random_shawe_taylor_prime_with_cert($bits);
 }
 
 sub random_strong_prime {
@@ -940,6 +948,7 @@ Version 0.40
   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
+  my $rand_prime = random_shawe_taylor_prime(256);  # as above
 
 
 =head1 DESCRIPTION
@@ -1081,8 +1090,9 @@ additional M-R tests with random bases with 
L</miller_rabin_random>.
 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.
+L<Math::Prime::Util/random_maurer_prime> or
+L<Math::Prime::Util/random_shawe_taylor_prime> which construct random
+provable primes.
 
 
 =head2 primes
@@ -2306,7 +2316,8 @@ Construct an n-bit provable prime, using the FastPrime 
algorithm of
 Ueli Maurer (1995).  This is the same algorithm used by L<Crypt::Primes>.
 Similar to L</random_nbit_prime>, 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 L<Math::Prime::Util::GMP>.
+with large bit sizes, install L<Math::Prime::Util::GMP>.  Also see
+L</random_shawe_taylor_prime>.
 
 The differences between this function and that in L<Crypt::Primes> are
 described in the L</"SEE ALSO"> section.
@@ -2337,6 +2348,39 @@ any other software that understands MPU primality 
certificates.
 The proof construction consists of a single chain of C<BLS3> types.
 
 
+=head2 random_shawe_taylor_prime
+
+  my $bigprime = random_shawe_taylor_prime(8192);
+
+Construct an n-bit provable prime, using the Shawe-Taylor algorithm in
+section C.6 of FIPS 186-4.  This uses 512 bits of randomness and SHA-256
+as the hash.  This is a slightly simpler and older (1986) method than
+Maurer's 1999 construction.  The primary reason to use this rather than
+Maurer's method is to use FIPS 186-4 algorithm.
+
+Similar to L</random_nbit_prime>, 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 L<Math::Prime::Util::GMP>.  Also see
+L</random_maurer_prime> and L</random_proven_prime>.
+
+Internally this additionally runs the BPSW probable prime test on every
+partial result, and constructs a primality certificate for the final
+result, which is verified.  These provide additional checks that the resulting
+value has been properly constructed.
+
+
+=head2 random_shawe_taylor_prime_with_cert
+
+  my($n, $cert) = random_shawe_taylor_prime_with_cert(4096)
+
+As with L</random_shawe_taylor_prime>, but returns a two-element array
+containing the n-bit provable prime along with a primality certificate.
+The certificate is the same as produced by L</prime_certificate> or
+L</is_provable_prime_with_cert>, and can be parsed by L</verify_prime> or
+any other software that understands MPU primality certificates.
+The proof construction consists of a single chain of C<Pocklington> types.
+
+
 
 =head1 UTILITY FUNCTIONS
 
diff --git a/lib/Math/Prime/Util/RandomPrimes.pm 
b/lib/Math/Prime/Util/RandomPrimes.pm
index 35b88ec..88f2e05 100644
--- a/lib/Math/Prime/Util/RandomPrimes.pm
+++ b/lib/Math/Prime/Util/RandomPrimes.pm
@@ -832,25 +832,28 @@ sub random_maurer_prime_with_cert {
   croak "Failure in random_maurer_prime, could not find a prime\n";
 } # End of random_maurer_prime
 
-sub random_shawe_taylor_prime {
+
+sub random_shawe_taylor_prime_with_cert {
   my $k = shift;
-  my $which = shift;
 
   my $seed;
-  {
-    # TODO: should go through RANDF
+  my $irandf = prime_get_config->{'irand'};
+  if (!defined $irandf) {
     if (!defined $_BRS) {
       require Bytes::Random::Secure;
       $_BRS = Bytes::Random::Secure->new(NonBlocking=>1);
     }
     $seed = $_BRS->bytes(512/8);
+  } else {
+    $seed = pack("L*", map { $irandf->() } 0 .. (512>>5));
   }
 
-  my($status,$prime,$prime_seed,$prime_gen_counter)
+  my($status,$prime,$prime_seed,$prime_gen_counter,$cert)
      = _ST_Random_prime($k, $seed);
-  croak "Shawe-Taylor random prime failure: loop overflow" unless $status;
+  croak "Shawe-Taylor random prime failure" unless $status;
+  croak "Shawe-Taylor random prime failure: prime $prime failed certificate 
verification!" unless verify_prime($cert);
 
-  return $prime;
+  return ($prime,$cert);
 }
 
 sub _seed_plus_one {
@@ -871,8 +874,8 @@ sub _ST_Random_prime {  # From FIPS 186-4
      unless defined $input_seed && length($input_seed) >= 32;
 
   if (!defined $Digest::SHA::VERSION) {
-    eval { require Digest::SHA; $Digest::SHA::VERSION >= 2.00; }
-      or do { croak "Must have Digest::SHA 2.00 or later"; };
+    eval { require Digest::SHA; $Digest::SHA::VERSION >= 4.00; }
+      or do { croak "Must have Digest::SHA 4.00 or later"; };
   }
 
   my $k2 = Math::BigInt->new(2)->bpow($k-1);
@@ -889,13 +892,16 @@ sub _ST_Random_prime {  # From FIPS 186-4
       $prime_gen_counter++;
       $seed = _seed_plus_one($seedp1);
       # c is small so we can provably test it.
-      return (1,$c,$seed,$prime_gen_counter) if is_prob_prime($c);
+      my ($isp, $cert) = is_provable_prime_with_cert($c);
+      return (1,$c,$seed,$prime_gen_counter,$cert) if $isp;
       return (0,0,0,0) if $prime_gen_counter > 4*$k;
     }
   }
-  my($status,$c0,$seed,$prime_gen_counter)
+  my($status,$c0,$seed,$prime_gen_counter,$cert)
      = _ST_Random_prime( (($k+1)>>1)+1, $input_seed);
   return (0,0,0,0) unless $status;
+  $cert = ($c0 < Math::BigInt->new("18446744073709551615"))
+          ? "" : _strip_proof_header($cert);
   my $iterations = int(($k + 255) / 256) - 1;  # SHA256 generates 256 bits
   my $old_counter = $prime_gen_counter;
   my $xstr = '';
@@ -906,12 +912,32 @@ sub _ST_Random_prime {  # From FIPS 186-4
   my $x = Math::BigInt->from_hex('0x'.$xstr);
   $x = $k2 + ($x % $k2);
   my $t = ($x + 2*$c0 - 1) / (2*$c0);
+  _make_big_gcds() if $_big_gcd_use < 0;
   while (1) {
     if (2*$t*$c0 + 1 > 2*$k2) { $t = ($k2 + 2*$c0 - 1) / (2*$c0); }
     my $c = 2*$t*$c0 + 1;
     $prime_gen_counter++;
-    # Only do this if we're pretty sure the candidate is prime.
-    if (is_prob_prime($c)) {
+
+    # Don't do the Pocklington check unless the candidate looks prime
+    my $looks_prime = 0;
+    if (MPU_USE_GMP) {
+      # MPU::GMP::is_prob_prime has fast tests built in.
+      $looks_prime = Math::Prime::Util::GMP::is_prob_prime($c);
+    } else {
+      # No GMP, so first do trial divisions, then a SPSP test.
+      $looks_prime = Math::BigInt::bgcd($c, 111546435)->is_one;
+      if ($looks_prime && $_big_gcd_use && $c > $_big_gcd_top) {
+        $looks_prime = Math::BigInt::bgcd($c, $_big_gcd[0])->is_one &&
+                       Math::BigInt::bgcd($c, $_big_gcd[1])->is_one &&
+                       Math::BigInt::bgcd($c, $_big_gcd[2])->is_one &&
+                       Math::BigInt::bgcd($c, $_big_gcd[3])->is_one;
+      }
+      $looks_prime = 0 if $looks_prime && !is_strong_pseudoprime($c, 3);
+    }
+
+    if ($looks_prime) {
+      # We really should do what Maurer does and just test a in 
(2,3,5,7,11,13).
+      # Instead we'll do the FIPS 186-4 method, which is rather stupid.
       my $astr = '';
       for my $i (0 .. $iterations) {
         $astr = Digest::SHA::sha256_hex($seed) . $astr;
@@ -923,7 +949,11 @@ sub _ST_Random_prime {  # From FIPS 186-4
       if (Math::BigInt::bgcd($z-1,$c)->is_one && 
$z->copy->bmodpow($c0,$c)->is_one) {
         croak "Shawe-Taylor random prime failure at ($k): $c not prime"
           unless is_prob_prime($c);
-        return (1, $c, $seed, $prime_gen_counter);
+        $cert = "[MPU - Primality Certificate]\nVersion 1.0\n\n" .
+                 "Proof for:\nN $c\n\n" .
+                 "Type Pocklington\nN $c\nQ $c0\nA $a\n" .
+                 $cert;
+        return (1, $c, $seed, $prime_gen_counter, $cert);
       }
     }
     return (0,0,0,0) if $prime_gen_counter > 4*$k + $old_counter;
@@ -1086,6 +1116,18 @@ Construct a random provable prime of C<n> bits using 
Maurer's FastPrime
 algorithm.  C<n> must be at least 2.  Returns a list of two items: the
 prime and the certificate.
 
+=head2 random_shawe_taylor_prime
+
+Construct a random provable prime of C<n> bits using Shawe-Taylor's
+algorithm.  C<n> must be at least 2.  The implementation is from
+FIPS 186-4 and uses SHA-256 with 512 bits of randomness.
+
+=head2 random_shawe_taylor_prime_with_cert
+
+Construct a random provable prime of C<n> bits using Shawe-Taylor's
+algorithm.  C<n> must be at least 2.  Returns a list of two items: the
+prime and the certificate.
+
 =head2 random_strong_prime
 
 Construct a random strong prime of C<n> bits.  C<n> must be at least 128.
diff --git a/t/16-randomprime.t b/t/16-randomprime.t
index 3fd3205..b51571f 100644
--- a/t/16-randomprime.t
+++ b/t/16-randomprime.t
@@ -7,13 +7,16 @@ use Test::More;
 #use Math::Random::MT::Auto qw/rand/;
 #sub rand { return 0.5; }
 use Math::Prime::Util qw/random_prime random_ndigit_prime random_nbit_prime
-                         random_maurer_prime random_proven_prime
+                         random_maurer_prime random_shawe_taylor_prime
+                         random_proven_prime
                          is_prime prime_set_config/;
 
 my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32;
 my $broken64 = (18446744073709550592 == ~0);
 my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
 my $maxbits = $use64 ? 64 : 32;
+my $do_st = 1;
+$do_st = 0 unless eval { require Digest::SHA; $Digest::SHA::VERSION >= 4.00; };
 
 my @random_to = (2, 3, 4, 5, 6, 7, 8, 9, 100, 1000, 1000000, 4294967295);
 
@@ -65,13 +68,13 @@ my %range_edge_empty = (
   "3842610774 to 3842611108" => [],
 );
 
-plan tests => 13+3+3+3
+plan tests => 13+3+3+3+3
               + (1 * scalar (keys %range_edge_empty))
               + (3 * scalar (keys %range_edge))
               + (2 * scalar (keys %ranges))
               + (2 * scalar @random_to)
               + (1 * scalar @random_ndigit_tests)
-              + (3 * scalar @random_nbit_tests)
+              + (4 * scalar @random_nbit_tests)
               + 2 + 4
               + 0;
 
@@ -104,6 +107,10 @@ ok(!eval { random_maurer_prime(undef); }, 
"random_maurer_prime(undef)");
 ok(!eval { random_maurer_prime(0); }, "random_maurer_prime(0)");
 ok(!eval { random_maurer_prime(-5); }, "random_maurer_prime(-5)");
 
+ok(!eval { random_shawe_taylor_prime(undef); }, 
"random_shawe_taylor_prime(undef)");
+ok(!eval { random_shawe_taylor_prime(0); }, "random_shawe_taylor_prime(0)");
+ok(!eval { random_shawe_taylor_prime(-5); }, "random_shawe_taylor_prime(-5)");
+
 while (my($range, $expect) = each (%range_edge_empty)) {
   my($low,$high) = $range =~ /(\d+) to (\d+)/;
   is( random_prime($low,$high), undef, "primes($low,$high) should return 
undef" );
@@ -155,6 +162,10 @@ foreach my $digits ( @random_ndigit_tests ) {
 foreach my $bits ( @random_nbit_tests ) {
   check_bits( random_nbit_prime($bits), $bits, "nbit" );
   check_bits( random_maurer_prime($bits), $bits, "Maurer" );
+  SKIP: {
+    skip "random Shawe-Taylor prime generation requires Digest::SHA",1 unless 
$do_st;
+    check_bits( random_shawe_taylor_prime($bits), $bits, "Shawe-Taylor" );
+  }
   check_bits( random_proven_prime($bits), $bits, "proven" );
 }
 

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