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

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

commit 2fea141a7a7a1f536fa018905250a61aeb01b3ba
Author: Dana Jacobsen <d...@acm.org>
Date:   Mon Jan 6 19:22:08 2014 -0800

    Performance tweaks (small) for bigints
---
 lib/Math/Prime/Util/ECAffinePoint.pm     | 49 ++++++++++++++++++++++++---
 lib/Math/Prime/Util/ECProjectivePoint.pm | 18 ++++++----
 lib/Math/Prime/Util/PrimalityProving.pm  | 57 ++++++++++++++++++--------------
 3 files changed, 88 insertions(+), 36 deletions(-)

diff --git a/lib/Math/Prime/Util/ECAffinePoint.pm 
b/lib/Math/Prime/Util/ECAffinePoint.pm
index d2d67d0..4041d17 100644
--- a/lib/Math/Prime/Util/ECAffinePoint.pm
+++ b/lib/Math/Prime/Util/ECAffinePoint.pm
@@ -72,12 +72,51 @@ sub _double {
   return ($x,$y);
 }
 
+sub _inplace_add {
+  my ($P1x, $P1y, $x, $y, $n) = @_;
+
+  if ($P1x == $x) {
+    my $t = ($P1y + $y) % $n;
+    if ($t == 0) {
+      ($_[2],$_[3]) = (Math::BigInt->bzero,Math::BigInt->bone);
+      return;
+    }
+  }
+  my $deltax = ($x - $P1x) % $n;
+  $deltax->bmodinv($n);
+  if ($deltax eq 'NaN') {
+    ($_[2],$_[3]) = (Math::BigInt->bzero,Math::BigInt->bone);
+    return;
+  }
+  my $deltay = ($y - $P1y) % $n;
+  my $m = ($deltay * $deltax) % $n;   # m = deltay / deltax
+
+  $_[2] = ($m*$m - $P1x - $x) % $n;
+  $_[3] = ($m*($P1x - $_[2]) - $P1y) % $n;
+}
+sub _inplace_double {
+  my($x, $y, $a, $n) = @_;
+  my $m = $y+$y;
+  $m->bmodinv($n);
+  if ($m eq 'NaN') {
+    ($_[0],$_[1]) = (Math::BigInt->bzero,Math::BigInt->bone);
+    return;
+  }
+  $m->bmul($x->copy->bmul($x)->bmul(3)->badd($a))->bmod($n);
+
+  my $xin = $x->copy;
+  $_[0] = ($m*$m - $x - $x) % $n;
+  $_[1] = ($m*($xin - $_[0]) - $y) % $n;
+}
+
 sub mul {
   my ($self, $k) = @_;
   my $x = $self->{'x'};
   my $y = $self->{'y'};
+  my $a = $self->{'a'};
   my $n = $self->{'n'};
   my $f = $self->{'f'};
+  $k = int($k->bstr) if ref($k) eq 'Math::BigInt' && $k < ''.~0;
 
   my $Bx = $n->copy->bzero;
   my $By = $n->copy->bone;
@@ -87,16 +126,16 @@ sub mul {
     if ( ($k % 2) != 0) {
       $k--;
       $f->bmul($Bx-$x)->bmod($n);
-      if    ($x == 0 && $y == 1)   { }
-      elsif ($Bx == 0 && $By == 1) { ($Bx,$By) = ($x,$y); }
-      else                         { ($Bx,$By) = $self->_add($x,$y,$Bx,$By); }
+      if    ($x->is_zero && $y->is_one)   { }
+      elsif ($Bx->is_zero && $By->is_one) { ($Bx,$By) = ($x,$y); }
+      else                                { _inplace_add($x,$y,$Bx,$By,$n); }
     } else {
       $k >>= 1;
       $f->bmul(2*$y)->bmod($n);
-      ($x,$y) = $self->_double($x,$y);
+      _inplace_double($x,$y,$a,$n);
     }
   }
-  $f = Math::BigInt::bgcd( $f, $n);
+  $f = Math::BigInt::bgcd($f, $n);
   $self->{'x'} = $Bx;
   $self->{'y'} = $By;
   $self->{'f'} = $f;
diff --git a/lib/Math/Prime/Util/ECProjectivePoint.pm 
b/lib/Math/Prime/Util/ECProjectivePoint.pm
index dd30eb8..f6343c0 100644
--- a/lib/Math/Prime/Util/ECProjectivePoint.pm
+++ b/lib/Math/Prime/Util/ECProjectivePoint.pm
@@ -53,20 +53,26 @@ sub _add3 {
   my $u = ($x2 - $z2) * ($x1 + $z1);
   my $v = ($x2 + $z2) * ($x1 - $z1);
 
-  my $upv2 = ($u + $v) ** 2;
-  my $umv2 = ($u - $v) ** 2;
+  my $upv2 = $u + $v;  $upv2->bmul($upv2);
+  my $umv2 = $u - $v;  $umv2->bmul($umv2);
 
-  return ( ($upv2*$zin) % $n, ($umv2*$xin) % $n );
+  $upv2->bmul($zin)->bmod($n);
+  $umv2->bmul($xin)->bmod($n);
+  return ($upv2, $umv2);
 }
 
 sub _double {
   my ($x, $z, $n, $d) = @_;
 
-  my $u = ($x + $z) ** 2;
-  my $v = ($x - $z) ** 2;
+  my $u = $x + $z;   $u->bmul($u);
+  my $v = $x - $z;   $v->bmul($v);
+
   my $w = $u - $v;
   my $t = $d * $w + $v;
-  return ( ($u * $v) % $n  ,  ($w * $t) % $n );
+
+  $u->bmul($v)->bmod($n);
+  $w->bmul($t)->bmod($n);
+  return ($u, $w);
 }
 
 sub mul {
diff --git a/lib/Math/Prime/Util/PrimalityProving.pm 
b/lib/Math/Prime/Util/PrimalityProving.pm
index 09ee681..69aebf4 100644
--- a/lib/Math/Prime/Util/PrimalityProving.pm
+++ b/lib/Math/Prime/Util/PrimalityProving.pm
@@ -114,17 +114,23 @@ sub primality_proof_bls75 {
   return @composite if is_strong_pseudoprime($n,2,15,325) == 0;
 
   $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt';
-  my $nm1 = $n-1;
-  my $A = $nm1->copy->bone;   # factored part
+  my $nm1 = $n->copy->bdec;
+  my $ONE = $nm1->copy->bone;
+  my $TWO = $ONE->copy->binc;
+  my $A = $ONE->copy;         # factored part
   my $B = $nm1->copy;         # unfactored part
-  my @factors = (2);
+  my @factors = ($TWO);
   croak "BLS75 error: n-1 not even" unless $nm1->is_even();
-  my $trial_B = 20000;
-  $trial_B = 500 if ! prime_get_config->{'xs'};
   {
-    while ($B->is_even) { $B /= 2; $A *= 2; }
-    my @tf = Math::Prime::Util::PP::trial_factor($B, $trial_B);
-    pop @tf if $tf[-1] > $trial_B;
+    while ($B->is_even) { $B->bdiv($TWO); $A->bmul($TWO); }
+    my @tf;
+    if ($B <= ''.~0 && prime_get_config->{'xs'}) {
+      @tf = Math::Prime::Util::trial_factor($B, 20000);
+      pop @tf if $tf[-1] > 20000;
+    } else {
+      @tf = Math::Prime::Util::PP::trial_factor($B, 500);
+      pop @tf if $tf[-1] > 500;
+    }
     foreach my $f (@tf) {
       next if $f == $factors[-1];
       push @factors, $f;
@@ -133,7 +139,7 @@ sub primality_proof_bls75 {
   }
   my @nstack;
   # nstack should only hold composites
-  if ($B == 1) {
+  if ($B->is_one) {
     # Completely factored.  Nothing.
   } elsif (is_prob_prime($B)) {
     push @factors, $B;
@@ -142,8 +148,8 @@ sub primality_proof_bls75 {
     push @nstack, $B;
   }
   while (@nstack) {
-    my ($s,$r) = $B->copy->bdiv($A->copy->bmul(2));
-    my $fpart = ($A+1) * (2*$A*$A + ($r-1) * $A + 1);
+    my ($s,$r) = $B->copy->bdiv($A->copy->bmul($TWO));
+    my $fpart = ($A+$ONE) * ($TWO*$A*$A + ($r-$ONE) * $A + $ONE);
     last if $n < $fpart;
 
     my $m = pop @nstack;
@@ -159,33 +165,33 @@ sub primality_proof_bls75 {
     next unless scalar @ftry > 1;
     # Process each factor
     foreach my $f (@ftry) {
-      croak "Invalid factoring: B=$B m=$m f=$f" if $f == 1 || $f == $m || 
($B%$f) != 0;
+      croak "Invalid factoring: B=$B m=$m f=$f" if $f == 1 || $f == $m || 
!$B->copy->bmod($f)->is_zero;
       if (is_prob_prime($f)) {
         push @factors, $f;
-        do { $B /= $f;  $A *= $f; } while (($B % $f) == 0);
+        do { $B /= $f;  $A *= $f; } while $B->copy->bmod($f)->is_zero;
       } else {
         push @nstack, $f;
       }
     }
   }
+  { # remove duplicate factors and make a sorted array of bigints
+    my %uf = map { $_ => 1 } @factors;
+    @factors = sort {$a<=>$b} map { Math::BigInt->new("$_") } keys %uf;
+  }
   # Just in case:
   foreach my $f (@factors) {
-    while (($B % $f) == 0) {
+    while ($B->copy->bmod($f)->is_zero) {
       $B /= $f;  $A *= $f;
     }
   }
-  { # remove duplicate factors and make a sorted array of bigints
-    my %uf = map { $_ => 1 } @factors;
-    @factors = sort {$a<=>$b} map { Math::BigInt->new("$_") } keys %uf;
-  }
   # Did we factor enough?
-  my ($s,$r) = $B->copy->bdiv($A->copy->bmul(2));
-  my $fpart = ($A+1) * (2*$A*$A + ($r-1) * $A + 1);
+  my ($s,$r) = $B->copy->bdiv($A->copy->bmul($TWO));
+  my $fpart = ($A+$ONE) * ($TWO*$A*$A + ($r-$ONE) * $A + $ONE);
   return (1,'') if $n >= $fpart;
   # Check we didn't mess up
   croak "BLS75 error: $A * $B != $nm1" unless $A*$B == $nm1;
   croak "BLS75 error: $A not even" unless $A->is_even();
-  croak "BLS75 error: A and B not coprime" unless Math::BigInt::bgcd($A, 
$B)==1;
+  croak "BLS75 error: A and B not coprime" unless Math::BigInt::bgcd($A, 
$B)->is_one;
 
   my $rtest = $r*$r - 8*$s;
   my $rtestroot = $rtest->copy->bsqrt;
@@ -203,10 +209,11 @@ sub primality_proof_bls75 {
     } else {
       $cert .= "Q[$qnum] $f\n";
     }
+    my $nm1_div_f = $nm1 / $f;
     foreach my $a (2 .. 10000) {
       my $ap = Math::BigInt->new($a);
-      next unless $ap->copy->bmodpow($nm1, $n) == 1;
-      next unless Math::BigInt::bgcd($ap->copy->bmodpow($nm1/$f, $n)->bsub(1), 
$n) == 1;
+      next unless $ap->copy->bmodpow($nm1, $n)->is_one;
+      next unless Math::BigInt::bgcd($ap->copy->bmodpow($nm1_div_f, $n)->bdec, 
$n)->is_one;
       $atext .= "A[$qnum] $a\n" unless $a == 2;
       $success = 1;
       last;
@@ -707,9 +714,9 @@ sub _verify_bls5 {
     my $a = $A[$i];
     my $q = $Q[$i];
     return _pfail "BLS5: $n failed A[i]^(N-1) mod N = 1"
-      unless $a->copy->bmodpow($nm1, $n) == 1;
+      unless $a->copy->bmodpow($nm1, $n)->is_one;
     return _pfail "BLS5: $n failed gcd(A[i]^((N-1)/Q[i])-1, N) = 1"
-      unless Math::BigInt::bgcd($a->copy->bmodpow($nm1/$q, $n)-1, $n) == 1;
+      unless Math::BigInt::bgcd($a->copy->bmodpow($nm1/$q, $n)->bdec, 
$n)->is_one;
   }
   ($n, @Q);
 }

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