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

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

commit 34da9f2d7a4c9cf4c601dc75c1e2e3dda21df4f2
Author: Dana Jacobsen <d...@acm.org>
Date:   Fri Apr 19 20:33:51 2013 -0700

    Tweak projective EC point
---
 lib/Math/Prime/Util/ECProjectivePoint.pm | 108 +++++++++++++++----------------
 lib/Math/Prime/Util/PP.pm                |  24 +++----
 2 files changed, 63 insertions(+), 69 deletions(-)

diff --git a/lib/Math/Prime/Util/ECProjectivePoint.pm 
b/lib/Math/Prime/Util/ECProjectivePoint.pm
index 1d062d8..c83110e 100644
--- a/lib/Math/Prime/Util/ECProjectivePoint.pm
+++ b/lib/Math/Prime/Util/ECProjectivePoint.pm
@@ -17,20 +17,18 @@ BEGIN {
 # in projective coordinates.
 
 sub new {
-  my ($class, $a, $b, $n, $x, $z) = @_;
-  $a = Math::BigInt->new("$a") unless ref($a) eq 'Math::BigInt';
-  $b = Math::BigInt->new("$b") unless ref($b) eq 'Math::BigInt';
+  my ($class, $c, $n, $x, $z) = @_;
+  $c = Math::BigInt->new("$c") unless ref($c) eq 'Math::BigInt';
   $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt';
   $x = Math::BigInt->new("$x") unless ref($x) eq 'Math::BigInt';
   $z = Math::BigInt->new("$z") unless ref($z) eq 'Math::BigInt';
 
   croak "n must be >= 2" unless $n >= 2;
-  $a->bmod($n);
-  $b->bmod($n);
+  $c->bmod($n);
 
   my $self = {
-    a => $a,
-    b => $b,
+    c => $c,
+    d => ($c + 2) >> 2,
     n => $n,
     x => $x,
     z => $z,
@@ -40,39 +38,39 @@ sub new {
   bless $self, $class;
   return $self;
 }
+ 
+sub _addx {
+  my ($x1, $x2, $xin, $n) = @_;
 
-sub _add {
-  my ($self, $x2, $z2, $x1, $z1, $xin, $n) = @_;
+  my $u = ($x2 - 1) * ($x1 + 1);
+  my $v = ($x2 + 1) * ($x1 - 1);
 
-  my $u = ( ($x2 - $z2) * ($x1 + $z1) ) % $n;
-  my $v = ( ($x2 + $z2) * ($x1 - $z1) ) % $n;
+  my $upv2 = ($u + $v) ** 2;
+  my $umv2 = ($u - $v) ** 2;
 
-  my $puv = $u + $v;
-  my $muv = $u - $v;
-
-  return ( ($puv*$puv) % $n, ($muv*$muv * $xin) % $n );
+  return ( $upv2 % $n, ($umv2*$xin) % $n );
 }
 
 sub _add3 {
-  my ($self, $x1, $z1, $x2, $z2, $xin, $zin, $n) = @_;
+  my ($x1, $z1, $x2, $z2, $xin, $zin, $n) = @_;
 
-  my $u = (($x2 - $z2) * ($x1 + $z1) ) % $n;
-  my $v = (($x2 + $z2) * ($x1 - $z1) ) % $n;
+  my $u = ($x2 - $z2) * ($x1 + $z1);
+  my $v = ($x2 + $z2) * ($x1 - $z1);
 
-  my $upv2 = (($u+$v) * ($u+$v)) % $n;
-  my $umv2 = (($u-$v) * ($u-$v)) % $n;
+  my $upv2 = ($u + $v) ** 2;
+  my $umv2 = ($u - $v) ** 2;
 
   return ( ($upv2*$zin) % $n, ($umv2*$xin) % $n );
 }
 
 sub _double {
-  my ($self, $x, $z, $n) = @_;
+  my ($x, $z, $n, $d) = @_;
 
-  my $u = $x + $z;   $u = ($u * $u) % $n;
-  my $v = $x - $z;   $v = ($v * $v) % $n;
+  my $u = ($x + $z) ** 2;
+  my $v = ($x - $z) ** 2;
   my $w = $u - $v;
-
-  return ( ($u*$v)%$n , ($w*($v+$w*$self->{'b'}))%$n );
+  my $t = $d * $w + $v;
+  return ( ($u * $v) % $n  ,  ($w * $t) % $n );
 }
 
 sub mul {
@@ -80,6 +78,7 @@ sub mul {
   my $x = $self->{'x'};
   my $z = $self->{'z'};
   my $n = $self->{'n'};
+  my $d = $self->{'d'};
 
   my ($x1, $x2, $z1, $z2);
 
@@ -87,28 +86,28 @@ sub mul {
   my $l = -1;
   while ($r != 1) { $r >>= 1; $l++ }
   if ($k & (1 << $l)) {
-    ($x2, $z2) = $self->_double($x, $z, $n);
-    ($x1, $z1) = $self->_add3($x2, $z2, $x, $z, $x, $z, $n);
-    ($x2, $z2) = $self->_double($x2, $z2, $n);
+    ($x2, $z2) = _double($x, $z, $n, $d);
+    ($x1, $z1) = _add3($x2, $z2, $x, $z, $x, $z, $n);
+    ($x2, $z2) = _double($x2, $z2, $n, $d);
   } else {
-    ($x1, $z1) = $self->_double($x, $z, $n);
-    ($x2, $z2) = $self->_add3($x, $z, $x1, $z1, $x, $z, $n);
+    ($x1, $z1) = _double($x, $z, $n, $d);
+    ($x2, $z2) = _add3($x, $z, $x1, $z1, $x, $z, $n);
   }
   $l--;
   while ($l >= 1) {
     if ($k & (1 << $l)) {
-      ($x1, $z1) = $self->_add3($x1, $z1, $x2, $z2, $x, $z, $n);
-      ($x2, $z2) = $self->_double($x2, $z2, $n);
+      ($x1, $z1) = _add3($x1, $z1, $x2, $z2, $x, $z, $n);
+      ($x2, $z2) = _double($x2, $z2, $n, $d);
     } else {
-      ($x2, $z2) = $self->_add3($x2, $z2, $x1, $z1, $x, $z, $n);
-      ($x1, $z1) = $self->_double($x1, $z1, $n);
+      ($x2, $z2) = _add3($x2, $z2, $x1, $z1, $x, $z, $n);
+      ($x1, $z1) = _double($x1, $z1, $n, $d);
     }
     $l--;
   }
   if ($k & 1) {
-    ($x, $z) = $self->_double($x2, $z2, $n);
+    ($x, $z) = _double($x2, $z2, $n, $d);
   } else {
-    ($x, $z) = $self->_add3($x2, $z2, $x1, $z1, $x, $z, $n);
+    ($x, $z) = _add3($x2, $z2, $x1, $z1, $x, $z, $n);
   }
 
   $self->{'x'} = $x;
@@ -121,20 +120,19 @@ sub add {
   croak "add takes a EC point"
     unless ref($other) eq 'Math::Prime::Util::ECProjectivePoint';
   croak "second point is not on the same curve"
-    unless $self->{'a'} == $other->{'a'} &&
-           $self->{'b'} == $other->{'b'} &&
+    unless $self->{'c'} == $other->{'c'} &&
            $self->{'n'} == $other->{'n'};
 
-  ($self->{'x'}, $self->{'z'}) = $self->_add3($self->{'x'}, $self->{'z'},
-                                              $other->{'x'}, $other->{'z'},
-                                              $self->{'x'}, $self->{'z'},
-                                              $self->{'n'});
+  ($self->{'x'}, $self->{'z'}) = _add3($self->{'x'}, $self->{'z'},
+                                       $other->{'x'}, $other->{'z'},
+                                       $self->{'x'}, $self->{'z'},
+                                       $self->{'n'});
   return $self;
 }
 
 sub double {
   my ($self) = @_;
-  ($self->{'x'}, $self->{'z'}) = $self->_double($self->{'x'}, $self->{'z'}, 
$self->{'n'});
+  ($self->{'x'}, $self->{'z'}) = _double($self->{'x'}, $self->{'z'}, 
$self->{'n'}, $self->{'d'});
   return $self;
 }
 
@@ -164,8 +162,8 @@ sub normalize {
   return $self;
 }
 
-sub a { return shift->{'a'}; }
-sub b { return shift->{'b'}; }
+sub c { return shift->{'c'}; }
+sub d { return shift->{'d'}; }
 sub n { return shift->{'n'}; }
 sub x { return shift->{'x'}; }
 sub z { return shift->{'z'}; }
@@ -179,7 +177,7 @@ sub is_infinity {
 sub copy {
   my $self = shift;
   return Math::Prime::Util::ECProjectivePoint->new(
-    $self->{'a'}, $self->{'b'}, $self->{'n'}, $self->{'x'}, $self->{'z'});
+    $self->{'c'}, $self->{'n'}, $self->{'x'}, $self->{'z'});
 }
 
 1;
@@ -207,7 +205,7 @@ Version 0.26
 =head1 SYNOPSIS
 
   # Create a point on a curve (a,b,n) with coordinates 0,1
-  my $ECP = Math::Prime::Util::ECProjectivePoint->new($a, $b, $n, 0, 1);
+  my $ECP = Math::Prime::Util::ECProjectivePoint->new($c, $n, 0, 1);
 
   # scalar multiplication by k.
   $ECP->mul($k)
@@ -228,17 +226,19 @@ To write.
 
 =head2 new
 
-  $point = Math::Prime::Util::ECProjectivePoint->new(a, b);
-
-Returns a new curve defined by a and b.
+  $point = Math::Prime::Util::ECProjectivePoint->new(c, n, x, z);
 
-=head2 a
+Returns a new point on the curve defined by the Montgomery parameter c.
 
-=head2 b
+=head2 c
 
 =head2 n
 
-Returns the C<a>, C<b>, or C<n> values that describe the curve.
+Returns the C<c>, C<d>, or C<n> values that describe the curve.
+
+=head2 d
+
+Returns the precalculated value of C<int( (c + 2) / 4 )>.
 
 =head2 x
 
@@ -248,7 +248,7 @@ Returns the C<x> or C<z> values that define the point on 
the curve.
 
 =head2 f
 
-Returns a possible factor found during EC multiplication.
+Returns a possible factor found after L</normalize>.
 
 =head2 add
 
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index f8f75a8..34a2ee1 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -1152,7 +1152,7 @@ my @_fsublist = (
   sub { ecm_factor    (shift,    10_000,  50_000, 10) },
   sub { holf_factor   (shift, 256*1024, $_holf_r); $_holf_r += 256*1024; },
   sub { pminus1_factor(shift,20_000_000); },
-  sub { ecm_factor    (shift,   100_000, 400_000, 10) },
+  sub { ecm_factor    (shift,   100_000, 800_000, 10) },
   sub { holf_factor   (shift, 512*1024, $_holf_r); $_holf_r += 512*1024; },
   sub { pbrent_factor (shift, 2048*1024, 13) },
   sub { holf_factor   (shift, 2048*1024, $_holf_r); $_holf_r += 2048*1024; },
@@ -1646,7 +1646,7 @@ sub ecm_factor {
     return @factors;
   }
 
-  $B2 = 1*$B1 unless defined $B2;
+  $B2 = 10*$B1 unless defined $B2;
   my $sqrt_b1 = int(sqrt($B1)+1);
 
   # Affine code.  About 3x slower than the projective, and no stage 2.
@@ -1690,8 +1690,7 @@ sub ecm_factor {
   my $irandf = Math::Prime::Util::_get_rand_func();
 
   foreach my $curve (1 .. $ncurves) {
-    my $sigma;
-    do { $sigma = $irandf->($n-1) } while ($sigma <= 5);
+    my $sigma = $irandf->($n-1-6) + 6;
     my ($u, $v) = ( ($sigma*$sigma - 5) % $n, (4 * $sigma) % $n );
     my ($x, $z) = ( ($u*$u*$u) % $n,  ($v*$v*$v) % $n );
     my $b = (4 * $x * $v) % $n;
@@ -1702,14 +1701,8 @@ sub ecm_factor {
     return _found_factor($f,$n, "ECM B1=$B1 curve $curve", @factors) if $f != 
1;
     $u = $b->copy->bmodinv($n);
     $a = (($a*$u) - 2) % $n;
-    $b = $a+2;
-    $b = ( (($b % 2) == 0) ? $b  : $b+$n ) >> 1;
-    $b = ( (($b % 2) == 0) ? $b  : $b+$n ) >> 1;
-    #$u = $z->copy->bmodinv($n);
-    #$x = ($x * $u) % $n;
-    #$z = $n-$n+1;
-
-    my $ECP = Math::Prime::Util::ECProjectivePoint->new($a, $b, $n, $x, $z);
+
+    my $ECP = Math::Prime::Util::ECProjectivePoint->new($a, $n, $x, $z);
     my $fm = $n-$n+1;
     my $i = 15;
 
@@ -1743,14 +1736,15 @@ sub ecm_factor {
         return _found_factor($f, $n, "ECM S2 B1=$B1 curve $curve");
       }
       my $S2x = $S2P->x;
+      my $S2d = $S2P->d;
       my @nqx = ($n-$n, $S2x);
 
       foreach my $i (2 .. 2*$D) {
         my($x2, $z2);
         if ($i % 2) {
-          ($x2, $z2) = $S2P->_add($nqx[($i+1)/2], $one, $nqx[($i-1)/2], $one, 
$S2x, $n);
+          ($x2, $z2) = 
Math::Prime::Util::ECProjectivePoint::_addx($nqx[($i-1)/2], $nqx[($i+1)/2], 
$S2x, $n);
         } else {
-          ($x2, $z2) = $S2P->_double($nqx[$i/2], $one, $n);
+          ($x2, $z2) = 
Math::Prime::Util::ECProjectivePoint::_double($nqx[$i/2], $one, $n, $S2d);
         }
         $nqx[$i] = $x2;
         #($f, $u, undef) = _extended_gcd($z2, $n);
@@ -1770,7 +1764,7 @@ sub ecm_factor {
       while ($m < ($B2+$D)) {
         if ($m != 1) {
           my $oldx = $S2x;
-          my ($x1, $z1) = $S2P->_add($S2x, $one, $nqx[2*$D], $one, $x, $n);
+          my ($x1, $z1) = 
Math::Prime::Util::ECProjectivePoint::_addx($nqx[2*$D], $S2x, $x, $n);
           $f = Math::BigInt::bgcd( $z1, $n );
           last if $f != 1;
           $u = $z1->copy->bmodinv($n);

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