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 40cb80d31de2db86cc5c9a96c70b07c2471ad065
Author: Dana Jacobsen <d...@acm.org>
Date:   Sun Jul 8 03:47:19 2012 -0600

    More random prime work
---
 lib/Math/Prime/Util.pm | 100 +++++++++++++++++++++++++++++++++----------------
 1 file changed, 68 insertions(+), 32 deletions(-)

diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 5d8408a..21daaf7 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -287,13 +287,13 @@ sub primes {
 #
 # The random_maurer_prime function uses Maurer's algorithm of course.
 #
-# The current code is pretty fast for native types, but very slow for bigints.
-#      37uS for   24-bit
-#     0.25s for   64-bit
+# The current code is reasonably fast for native, but very slow for bigints.
+#      70uS for   24-bit
+#     0.01s for   64-bit
 #     0.2s  for  128-bit
-#     1.3s  for  256-bit
-#     9s    for  512-bit
-#   3m      for 1024-bit
+#     1s    for  256-bit
+#    10s    for  512-bit
+#   1m      for 1024-bit
 #  ~4m      for 2048-bit
 # ~80m      for 4096-bit
 #
@@ -330,7 +330,7 @@ sub primes {
     my $max = int($range) + 1;
     my $offset = 0;
     while ($max > 1) {
-      if ($max <= $rand_max_val) { $offset += $irandf->($max); last; }
+      if ($max <= 31) { $offset += $irandf->($max); last; }
       my $part = $max >> 1;
       $part++ if ($max & 1) && $get_rand_bit->();
       $offset += $part if $get_rand_bit->();
@@ -343,13 +343,15 @@ sub primes {
   # ranges the two edges are selected with slightly higher priority because
   # we're approximating 1/r using powers of 2.  The error rapidly reduces
   # as r increases.  By calling out to irandf when max is small enough we can
-  # make it basically go away.
+  # mitigate it.
   #
   # The other implementation choice I can think of is to call irandf a bunch
   # of times to get a random number R >= r.  Let m = int(R/r).  If R < m*r
   # then return R % m.  Repeat otherwise.  This description isn't quite right
   # in that we want to generate R with at least as many random bits as r, not
   # necessarily greater, and m is related to the bits in each.
+  #
+  # Lastly I could do a recursive partition.
 
 
   # Sub to call with low and high already primes and verified range.
@@ -401,19 +403,36 @@ sub primes {
 
     # Since we have an arbitrary range and not a power of two, I don't see how
     # Fouque's algorithm A1 could be used (where we generate lower bits and
-    # generate random sets of upper).  What I'm doing is pulling out 2^31 lower
-    # bits, then randomly select all the uppers.  We iterate adding in the 
lower
-    # bits.
-
-    my $srange = $oddrange - $rand_max_val - 1;
-    my $offset = $get_rand_range->($srange);
-    my $primelow = $low + 2 * $offset;
+    # generate random sets of upper).  Similarly trying to simply generate
+    # upper bits is full of ways to trip up and get non-uniform results.
+    #
+    # What I'm doing here is:
+    #
+    #   1) divide the range into semi-evenly sized partitions, where each part
+    #      is as close to $rand_max_val as we can.
+    #   2) randomly select one of the partitions.
+    #   3) iterate choosing random values within the partition.
+
+    my $nbins   = int( ($oddrange + $rand_max_val - 1) / $rand_max_val );
+    my $binsize = int( ($oddrange + $nbins - 1) / $nbins );
+    my $nparts  = int( $oddrange / $binsize );
+    
+    my $rpart = $get_rand_range->($nparts);
+    #my $rpart = (($irandf->($rand_max_val) << 31) + $irandf->($rand_max_val)) 
% $nparts;
+
+    my $primelow = $low + 2 * $binsize * $rpart;
+    my $partsize = ($rpart < $nparts) ? $binsize
+                                      : $oddrange - ($nparts * $binsize);
+    $partsize = int($partsize->bstr) if ref($partsize) eq 'Math::BigInt';
+    #warn "range $oddrange  = $nparts * $binsize + ", $oddrange - ($nparts * 
$binsize), "\n";
+    #warn "  chose part $rpart size $partsize\n";
+    #warn "  primelow is $low + 2 * $binsize * $rpart = $primelow\n";
 
     # Generate random numbers in the interval until one is prime.
     my $loop_limit = 2000 * 1000;  # To protect against broken rand
     while (1) {
-      $prime = $primelow + ( 2 * $irandf->($rand_max_val) );
-      die "$prime > $high" if $prime > $high;
+      $prime = $primelow + ( 2 * $irandf->($partsize) );
+      croak "random prime failure, $prime > $high" if $prime > $high;
       croak "Random function broken?" if $loop_limit-- < 0;
       if (ref($prime) eq 'Math::BigInt') {
         next if $prime > 53 && Math::BigInt::bgcd($prime, 
"16294579238595022365") != 1;
@@ -551,15 +570,21 @@ sub primes {
       #warn "$n passes final gcd\n";
 
       # Or via a different method, where we check q >= n**1/3 and also do
-      # some tests on x & y from 2R = xq+y.  Crypt::Primes does the q test
-      # but doesn't seem to do the x/y and perfect square portions.
+      # some tests on x & y from 2R = xq+y (see Lemma 2 from Maurer's paper).
+      # Crypt::Primes does the q test but doesn't seem to do the x/y and
+      # perfect square portions.
       #   next if ($q <= $n->copy->bpow(1/3));
-      #   next if ....
+      #   my $x = (2*$R)->bdiv($q)->bfloor;
+      #   my $y = 2*$R - $x*$q;
+      #   my $z = $y*$y - 4*$x;
+      #   next if $z == 0;
+      #   next if $z is a perfect square
+      # Menezes seems to imply only the q test needs to be done.
 
       # Finally, verify with a BPSW test on the result.  This will either,
       #  1) save us from accidently outputing a non-prime due to some mistake
       #  2) make history by finding the first known BPSW pseudo-prime
-      die "Maurer prime $n failed BPSW" unless is_prob_prime($n);
+      croak "Maurer prime $n failed BPSW" unless is_prob_prime($n);
       #warn "     and passed BPSW.\n";
 
       return $n;
@@ -1489,7 +1514,6 @@ the obvious Monte Carlo method is used, where random 
numbers in the range are
 selected until one is prime.  For even larger ranges, a method similar to that
 of Fouque and Tibouchi (2011) algorithm A1 is used.
 
-
 Perl's L<rand> function is normally called, but if the sub C<main::rand>
 exists, it will be used instead.  When called with no arguments it should
 return a float value between 0 and 1-epsilon, with 31 bits of randomness.
@@ -1501,9 +1525,10 @@ Examples:
   # Use a custom random function
   sub rand { ... }
 
-If you want cryptographically secure primes, I suggest looking at
-L<Crypt::Primes> for now.  At minimum you should use a better source of
-random numbers, such as L<Crypt::Random>.
+If you want cryptographically secure primes, at minimum a better source of
+random numbers should be used, e.g. L<Crypt::Random>.  Until this module
+has more testing, I would point the user to L<Crypt::Primes> for production
+use.
 
 
 =head2 random_ndigit_prime
@@ -1531,13 +1556,24 @@ This the trivial algorithm to select primes from a 
range.  This gives a uniform
 distribution, however it is quite slow for bigints, where the C<is_prime>
 function is a limiter.
 
-The differences between this function and what is used by L<Crypt::Primes>
-include: (1) this function generates probable primes (albeit using BPSW) while
-the latter is provable primes; (2) this function is really fast for native
-bit sizes, but ridiculously slow in its current implementation when run on
-very large numbers of bits -- L<Crypt::Primes> is quite fast for large bits;
-(3) this function requires no external libraries while the latter requires
-L<Math::Pari>; (4) the latter has some useful options for cryptography.
+
+=head2 random_maurer_prime
+
+  use bigint;  my $bigprime = random_maurer_prime(512);
+
+Construct an n-bit provable prime, using the algorithm of Ueli Maurer (1995).
+This is the same algorithm used by L<Crypt::Primes>.
+
+The differences between this function and that in L<Crypt::Primes> include
+(1) this function is really fast for native bit sizes, but ridiculously slow
+in its current implementation when run on very large numbers of bits; (2) no
+external libraries are used for this module, while C::P uses L<Math::Pari>;
+(3) C::P uses a modified version of final acceptance criteria
+(C<q E<LT> n**(1/3)> without the rest of Lemma 2), while this module uses the
+original set followed by a BPSW probable prime test to give some extra
+assurance against code error; (4) C::P  has some useful options for
+cryptography, and (5) C::P is hardcoded to use Crypt::Random, while this
+function will use whatever you set C<rand> to (this is both good and bad).
 
 
 =head2 moebius

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