File Coverage

blib/lib/Math/Prime/Util/ECProjectivePoint.pm

Criterion	Covered	Total	%
statement	95	108	87.9
branch	14	22	63.6
condition	0	6	0.0
subroutine	16	21	76.1
pod	13	13	100.0
total	138	170	81.1

package Math::Prime::Util::ECProjectivePoint;
use strict;
use warnings;
use Carp qw/carp croak confess/;

BEGIN {
  $Math::Prime::Util::ECProjectivePoint::AUTHORITY = 'cpan:DANAJ';
  $Math::Prime::Util::ECProjectivePoint::VERSION = '0.73';
}

BEGIN {
  do { require Math::BigInt;  Math::BigInt->import(try=>"GMP,Pari"); }
    unless defined $Math::BigInt::VERSION;
}

# Pure perl (with Math::BigInt) manipulation of Elliptic Curves
# in projective coordinates.

sub new {
  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;
  $c->bmod($n);

  my $self = {
    c => $c,
    d => ($c + 2) >> 2,
    n => $n,
    x => $x,
    z => $z,
    f => $n-$n+1,
  };

  bless $self, $class;
  return $self;
}

sub _addx {
  my ($x1, $x2, $xin, $n) = @_;

  my $u = ($x2 - 1) * ($x1 + 1);
  my $v = ($x2 + 1) * ($x1 - 1);

  my $upv2 = ($u + $v) ** 2;
  my $umv2 = ($u - $v) ** 2;

  return ( $upv2 % $n, ($umv2*$xin) % $n );
}

sub _add3 {
  my ($x1, $z1, $x2, $z2, $xin, $zin, $n) = @_;

  my $u = ($x2 - $z2) * ($x1 + $z1);
  my $v = ($x2 + $z2) * ($x1 - $z1);

  my $upv2 = $u + $v;  $upv2->bmul($upv2);
  my $umv2 = $u - $v;  $umv2->bmul($umv2);

  $upv2->bmul($zin)->bmod($n);
  $umv2->bmul($xin)->bmod($n);
  return ($upv2, $umv2);
}

sub _double {
  my ($x, $z, $n, $d) = @_;

  my $u = $x + $z;   $u->bmul($u);
  my $v = $x - $z;   $v->bmul($v);

  my $w = $u - $v;
  my $t = $d * $w + $v;

  $u->bmul($v)->bmod($n);
  $w->bmul($t)->bmod($n);
  return ($u, $w);
}

sub mul {
  my ($self, $k) = @_;
  my $x = $self->{'x'};
  my $z = $self->{'z'};
  my $n = $self->{'n'};
  my $d = $self->{'d'};

  my ($x1, $x2, $z1, $z2);

  my $r = --$k;
  my $l = -1;
  while ($r != 1) { $r >>= 1; $l++ }
  if ($k & (1 << $l)) {
    ($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) = _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) = _add3($x1, $z1, $x2, $z2, $x, $z, $n);
      ($x2, $z2) = _double($x2, $z2, $n, $d);
    } else {
      ($x2, $z2) = _add3($x2, $z2, $x1, $z1, $x, $z, $n);
      ($x1, $z1) = _double($x1, $z1, $n, $d);
    }
    $l--;
  }
  if ($k & 1) {
    ($x, $z) = _double($x2, $z2, $n, $d);
  } else {
    ($x, $z) = _add3($x2, $z2, $x1, $z1, $x, $z, $n);
  }

  $self->{'x'} = $x;
  $self->{'z'} = $z;
  return $self;
}

sub add {
  my ($self, $other) = @_;
  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->{'c'} == $other->{'c'} &&
           $self->{'n'} == $other->{'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'}) = _double($self->{'x'}, $self->{'z'}, $self->{'n'}, $self->{'d'});
  return $self;
}

#sub _extended_gcd {
#  my ($a, $b) = @_;
#  my $zero = $a-$a;
#  my ($x, $lastx, $y, $lasty) = ($zero, $zero+1, $zero+1, $zero);
#  while ($b != 0) {
#    my $q = int($a/$b);
#    ($a, $b) = ($b, $a % $b);
#    ($x, $lastx) = ($lastx - $q*$x, $x);
#    ($y, $lasty) = ($lasty - $q*$y, $y);
#  }
#  return ($a, $lastx, $lasty);
#}

sub normalize {
  my ($self) = @_;
  my $n = $self->{'n'};
  my $z = $self->{'z'};
  #my ($f, $u, undef) = _extended_gcd( $z, $n );
  my $f = Math::BigInt::bgcd( $z, $n );
  my $u = $z->copy->bmodinv($n);
  $self->{'x'} = ( $self->{'x'} * $u ) % $n;
  $self->{'z'} = $n-$n+1;
  $self->{'f'} = ($f * $self->{'f'}) % $n;
  return $self;
}

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'}; }
sub f { return shift->{'f'}; }

sub is_infinity {
  my $self = shift;
  return ($self->{'x'}->is_zero() && $self->{'z'}->is_one());
}

sub copy {
  my $self = shift;
  return Math::Prime::Util::ECProjectivePoint->new(
    $self->{'c'}, $self->{'n'}, $self->{'x'}, $self->{'z'});
}

1;

__END__