File Coverage

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

Criterion	Covered	Total	%
statement	74	114	64.9
branch	19	46	41.3
condition	7	25	28.0
subroutine	10	19	52.6
pod	10	10	100.0
total	120	214	56.0

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

BEGIN {
  $Math::Prime::Util::ECAffinePoint::AUTHORITY = 'cpan:DANAJ';
  $Math::Prime::Util::ECAffinePoint::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 affine coordinates.  Should be split into a point class.

sub new {
  my ($class, $a, $b, $n, $x, $y) = @_;
  $a = Math::BigInt->new("$a") unless ref($a) eq 'Math::BigInt';
  $b = Math::BigInt->new("$b") unless ref($b) 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';
  $y = Math::BigInt->new("$y") unless ref($y) eq 'Math::BigInt';

  croak "n must be >= 2" unless $n >= 2;
  $a->bmod($n);
  $b->bmod($n);

  my $self = {
    a => $a,
    b => $b,
    n => $n,
    x => $x,
    y => $y,
    f => $n->copy->bone,
  };

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

sub _add {
  my ($self, $P1x, $P1y, $P2x, $P2y) = @_;
  my $n = $self->{'n'};

  if ($P1x == $P2x) {
    my $t = ($P1y + $P2y) % $n;
    return (Math::BigInt->bzero,Math::BigInt->bone) if $t == 0;
  }
  my $deltax = ($P2x - $P1x) % $n;
  $deltax->bmodinv($n);
  return (Math::BigInt->bzero,Math::BigInt->bone) if $deltax eq "NaN";

  my $deltay = ($P2y - $P1y) % $n;
  my $m = ($deltay * $deltax) % $n;   # m = deltay / deltax

  my $x = ($m*$m - $P1x - $P2x) % $n;
  my $y = ($m*($P1x - $x) - $P1y) % $n;
  return ($x,$y);
}

sub _double {
  my ($self, $P1x, $P1y) = @_;
  my $n = $self->{'n'};

  my $m = 2*$P1y;
  $m->bmodinv($n);
  return (Math::BigInt->bzero,Math::BigInt->bone) if $m eq "NaN";

  $m = ((3*$P1x*$P1x + $self->{'a'}) * $m) % $n;

  my $x = ($m*$m - 2*$P1x) % $n;
  my $y = ($m*($P1x - $x) - $P1y) % $n;
  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'};
  if (ref($k) eq 'Math::BigInt' && $k < ''.~0) {
    if ($] >= 5.008 || ~0 == 4294967295) {
      $k = int($k->bstr);
    } elsif ($] < 5.008 && ~0 > 4294967295 && $k < 562949953421312) {
      $k = unpack('Q',pack('Q',$k->bstr));
    }
  }

  my $Bx = $n->copy->bzero;
  my $By = $n->copy->bone;
  my $v = 1;

  while ($k > 0) {
    if ( ($k % 2) != 0) {
      $k--;
      $f->bmul($Bx-$x)->bmod($n);
      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);
      _inplace_double($x,$y,$a,$n);
    }
  }
  $f = Math::BigInt::bgcd($f, $n);
  $self->{'x'} = $Bx;
  $self->{'y'} = $By;
  $self->{'f'} = $f;
  return $self;
}

sub add {
  my ($self, $other) = @_;
  croak "add takes a EC point"
    unless ref($other) eq 'Math::Prime::Util::ECAffinePoint';
  croak "second point is not on the same curve"
    unless $self->{'a'} == $other->{'a'} &&
           $self->{'b'} == $other->{'b'} &&
           $self->{'n'} == $other->{'n'};

  ($self->{'x'}, $self->{'y'}) = $self->_add($self->{'x'}, $self->{'y'},
                                             $other->{'x'}, $other->{'y'});
  return $self;
}


sub a { return shift->{'a'}; }
sub b { return shift->{'b'}; }
sub n { return shift->{'n'}; }
sub x { return shift->{'x'}; }
sub y { return shift->{'y'}; }
sub f { return shift->{'f'}; }

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

1;

__END__