chiark - git - mdw - catacomb-perl/blob - Catacomb/Field.pm

   1 # -*-perl-*-
   2 #
   3 # $Id$
   4 #
   5 # Field abstraction
   6 #
   7 # (c) 2004 Straylight/Edgeware
   8 #
   9
  10 #----- Licensing notice -----------------------------------------------------
  11 #
  12 # This file is part of the Perl interface to Catacomb.
  13 #
  14 # Catacomb/Perl is free software; you can redistribute it and/or modify
  15 # it under the terms of the GNU General Public License as published by
  16 # the Free Software Foundation; either version 2 of the License, or
  17 # (at your option) any later version.
  18 #
  19 # Catacomb/Perl is distributed in the hope that it will be useful,
  20 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  21 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22 # GNU General Public License for more details.
  23 #
  24 # You should have received a copy of the GNU General Public License
  25 # along with Catacomb/Perl; if not, write to the Free Software Foundation,
  26 # Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27
  28 #----- Abstract fields ------------------------------------------------------
  29
  30 package Catacomb::Field;
  31 use Carp;
  32 use Catacomb::Base;
  33 use Catacomb::Cache;
  34
  35 $cache = Catacomb::Cache->new();
  36
  37 sub intern {
  38   croak("USage: Catacomb::Field::intern(f)") unless @_ == 1;
  39   my ($f) = @_;
  40   return $cache->intern($f);
  41 }
  42
  43 sub elt {
  44   croak("Usage: Catacomb::Field::elt(f, x)") unless @_ == 2;
  45   my ($f, $x) = @_;
  46   return Catacomb::Field::Elt->new($f, $x);
  47 }
  48
  49 sub zero {
  50   croak("Usage: Catacomb::Field::zero(f)") unless @_ == 1;
  51   my ($f) = @_;
  52   return Catacomb::Field::Elt->new($f, $f->_zero());
  53 }
  54
  55 sub one {
  56   croak("Usage: Catacomb::Field::one(f)") unless @_ == 1;
  57   my ($f) = @_;
  58   return Catacomb::Field::Elt->new($f, $f->_one());
  59 }
  60
  61 sub rand {
  62   croak("Usage: Catacomb::Field::rand(f, [rng])")
  63     unless @_ >= 1 && @_ <= 2;
  64   my ($f, $rng) = @_;
  65   $rng ||= $Catacomb::random;
  66   return Catacomb::Field::Elt->new($f, $f->_one($rng));
  67 }
  68
  69 sub div {
  70   croak("Usage: Catacomb::Field::div(f, x, y)") unless @_ == 3;
  71   my ($f, $x, $y) = @_;
  72   return $f->mul($x, $f->inv($y));
  73 }
  74
  75 sub primecurve {
  76   croak("Usage: Catacomb::Field::primecurve(f, a, b)") unless @_ == 3;
  77   my ($f, $a, $b) = @_;
  78   croak("not a prime field") unless $f->type == Catacomb::FTY_PRIME;
  79   return Catacomb::EC::Curve->prime($f, $a, $b);
  80 }
  81
  82 sub primeprojcurve {
  83   croak("Usage: Catacomb::Field::primeprojcurve(f, a, b)") unless @_ == 3;
  84   my ($f, $a, $b) = @_;
  85   croak("not a prime field") unless $f->type == Catacomb::FTY_PRIME;
  86   return Catacomb::EC::Curve->primeproj($f, $a, $b);
  87 }
  88
  89 sub bincurve {
  90   croak("Usage: Catacomb::Field::bincurve(f, a, b)") unless @_ == 3;
  91   my ($f, $a, $b) = @_;
  92   croak("not a prime field") unless $f->type == Catacomb::FTY_BINARY;
  93   return Catacomb::EC::Curve->bincurve($f, $a, $b);
  94 }
  95
  96 sub binprojcurve {
  97   croak("Usage: Catacomb::Field::binprojcurve(f, a, b)") unless @_ == 3;
  98   my ($f, $a, $b) = @_;
  99   croak("not a prime field") unless $f->type == Catacomb::FTY_BINARY;
 100   return Catacomb::EC::Curve->binproj($f, $a, $b);
 101 }
 102
 103 #----- Field elements -------------------------------------------------------
 104
 105 package Catacomb::Field::Elt;
 106 use Carp;
 107 use Catacomb::Base;
 108
 109 sub _elt { bless [@_], Catacomb::Field::Elt; }
 110
 111 sub new {
 112   croak("Usage: Catacomb::Field::Elt::new(me, f, x)"), unless @_ == 3;
 113   my ($me, $f, $x) = @_;
 114   my $r;
 115   ($f, $r) = $f->intern();
 116   return _elt($f->in($x), $f, $r);
 117 }
 118
 119 sub field {
 120   croak("Usage: Catacomb::Field::Elt::field(e)") unless @_ == 1;
 121   return $_[0][1];
 122 }
 123
 124 sub value {
 125   croak("Usage: Catacomb::Field::Elt::value(e)") unless @_ == 1;
 126   return $_[0][1]->out($_[0][0]);
 127 }
 128
 129 sub elt {
 130   croak("Usage: Catacomb::Field::Elt::elt(e, x)") unless @_ == 2;
 131   my ($e, $x) = @_;
 132   my $f = $e->[1];
 133   return _elt($f->in($x), $f, $e->[2]);
 134 }
 135
 136 sub tostring {
 137   croak("Usage: Catacomb::Field::Elt::tostring(e, [radix])")
 138     unless @_ >= 1 && @_ <= 2;
 139   my ($e, $radix) = @_;
 140   $radix = 16 unless defined($radix);
 141   return $e->value()->tostring($radix);
 142 }
 143
 144 sub _convert {
 145   my ($x, $f, $r) = @_;
 146   if (UNIVERSAL::isa($x, Catacomb::Field::Elt)) {
 147     croak("field mismatch") unless $f == $x->[1];
 148     return $x;
 149   }
 150   if ($x == 0) {
 151     return _elt($f->_zero(), $f, $r);
 152   }
 153   if ($x == 1) {
 154     return _elt($f, $f->_one(), $f, $r);
 155   }
 156   croak("can't convert to field element");
 157 }
 158
 159 sub _binop {
 160   my ($op, $x, $y, $swap) = @_;
 161   my $f = $x->[1];
 162   my $r = $x->[2];
 163   $y = _convert($y, $f, $r);
 164   my $z = $swap ?
 165     &$op($f, $x->[0], $y->[0]) :
 166     &$op($f, $y->[0], $x->[0]);
 167   return _elt($z, $f, $r);
 168 }
 169
 170 sub _unop {
 171   my ($op, $x) = @_;
 172   my $f = $x->[1];
 173   my $r = $x->[2];
 174   my $z = &$op($f, $x->[0]);
 175   return _elt($z, $f, $r);
 176 }
 177
 178 sub exp {
 179   croak("Usage: Catacomb::Field::Elt::exp(x, n)") unless @_ == 2;
 180   my ($x, $n) = @_;
 181   my ($xx, $f, $fr) = @$x;
 182   return _elt($f->exp($xx, $n), $f, $fr);
 183 }
 184
 185 sub sqrt {
 186   croak("Usage: Catacomb::Field::Elt::sqrt(x)") unless @_ == 1;
 187   my ($x) = @_;
 188   my ($xx, $f, $fr) = @$x;
 189   return _elt($f->sqrt($xx), $f, $fr);
 190 }
 191
 192 sub zerop {
 193   croak("Usage: Catacomb::Field::Elt::zerop(x)") unless @_ == 1;
 194   my ($x) = @_;
 195   my ($xx, $f, $fr) = @$x;
 196   return $f->zero($xx);
 197 }
 198
 199 sub _eq {
 200   my ($x, $y) = @_;
 201   $y = _convert($y, $x->[1], $x->[2]);
 202   return Catacomb::MP::eq($x->[0], $y->[0]);
 203 }
 204
 205 use overload
 206   '+' => sub { _binop(\&Catacomb::Field::add, @_); },
 207   '-' => sub { _binop(\&Catacomb::Field::sub, @_); },
 208   '*' => sub { _binop(\&Catacomb::Field::mul, @_); },
 209   '/' => sub { _binop(\&Catacomb::Field::div, @_); },
 210   '**' => sub { &exp($_[0], $_[1]); },
 211   '==' => sub { _eq(@_); },
 212   '!=' => sub { !_eq(@_); },
 213   'eq' => sub { _eq(@_); },
 214   'ne' => sub { !_eq(@_); },
 215   '""' => sub { "0x" . $_[0]->tostring(16); },
 216   '0+' => sub { $_[0][1]->toint(); },
 217   'sqrt' => sub { _unop(\&Catacomb::Field::sqrt, @_); },
 218   'neg' => sub { _unop(\&Catacomb::Field::neg, @_); };
 219
 220 sub inv { _unop(\&Catacomb::Field::inv, @_); }
 221
 222 #----- That's all, folks ----------------------------------------------------