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