| 1 | # -*-perl-*- |
| 2 | # |
| 3 | # $Id$ |
| 4 | # |
| 5 | # Binary polynomial arithmetic |
| 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 | #----- Binary polynomials --------------------------------------------------- |
| 29 | |
| 30 | package Catacomb::GF; |
| 31 | use Catacomb::Base; |
| 32 | use Catacomb::MP; |
| 33 | use Carp; |
| 34 | |
| 35 | @ISA = qw(Catacomb::MP); |
| 36 | |
| 37 | sub gf { new(Catacomb::GF, $_[0]); } |
| 38 | sub gf_loadb { loadb(Catacomb::GF, $_[0]); } |
| 39 | sub gf_loadl { loadl(Catacomb::GF, $_[0]); } |
| 40 | sub gf_fromstring { fromstring(Catacomb::GF, $_[0]); } |
| 41 | |
| 42 | use overload |
| 43 | '+' => sub { _binop(\&add, @_); }, |
| 44 | '-' => sub { _binop(\&add, @_); }, |
| 45 | '*' => sub { _binop(\&mul, @_); }, |
| 46 | '/' => sub { _binop(\&div, @_); }, |
| 47 | '%' => sub { _binop(\&mod, @_); }, |
| 48 | '&' => sub { _binop(\&Catacomb::MP::and, @_); }, |
| 49 | '|' => sub { _binop(\&Catacomb::MP::or, @_); }, |
| 50 | '^' => sub { _binop(\&Catacomb::MP::xor, @_); }, |
| 51 | '**' => sub { _binop(\&pow, @_); }, |
| 52 | '>>' => sub { new(undef, &Catacomb::MP::lsr(@_[0, 1])); }, |
| 53 | '<<' => sub { new(undef, &Catacomb::MP::lsl(@_[0, 1])); }, |
| 54 | '~' => sub { new(undef, &Catacomb::MP::not($_[0])) }, |
| 55 | '==' => sub { _binop(\&Catacomb::MP::eq, @_); }, |
| 56 | '!=' => sub { !_binop(\&Catacomb::MP::eq, @_); }, |
| 57 | 'eq' => sub { _binop(\&Catacomb::MP::eq, @_); }, |
| 58 | 'ne' => sub { !_binop(\&Catacomb::MP::eq, @_); }, |
| 59 | '""' => sub { "0x" . &Catacomb::MP::tostring($_[0], 16); }, |
| 60 | 'neg' => sub { $_[0]; }, |
| 61 | '0+' => sub { &Catacomb::MP::toint($_[0]); }; |
| 62 | |
| 63 | sub binpolyfield { |
| 64 | croak("Usage: Catacomb::GF::binpolyfield(p)") unless @_ == 1; |
| 65 | return Catacomb::Field->binpoly($_[0]); |
| 66 | } |
| 67 | |
| 68 | sub binnormfield { |
| 69 | croak("Usage: Catacomb::GF::binnormfield(p, beta)") unless @_ == 2; |
| 70 | return Catacomb::Field->binnormfield($_[0], $_[1]); |
| 71 | } |
| 72 | |
| 73 | sub binpolygroup { |
| 74 | croak("Usage: Catacomb::GF::binpolygroup(p, g, q)") unless @_ == 3; |
| 75 | return Catacomb::Group->binary(@_); |
| 76 | } |
| 77 | |
| 78 | sub mod { (&div($_[0], $_[1]))[1]; } |
| 79 | |
| 80 | sub pow { |
| 81 | croak("Usage: Catacomb::GF::pow(a, b)") unless @_ == 2; |
| 82 | my ($a, $b) = @_; |
| 83 | my $r = Catacomb::GF->new(1); |
| 84 | while ($b) { |
| 85 | $r *= $a if $b & 1; |
| 86 | $a = sqr($a); |
| 87 | $b >>= 1; |
| 88 | } |
| 89 | return $r; |
| 90 | } |
| 91 | |
| 92 | sub _binop { |
| 93 | my ($func, $a, $b, $flag) = @_; |
| 94 | return new(undef, $flag ? &$func($b, $a) : &$func($a, $b)); |
| 95 | } |
| 96 | |
| 97 | sub modexp { |
| 98 | croak("Usage: Catacomb::GF::modexp(p, g, x)") unless @_ == 3; |
| 99 | my ($p, $g, $x) = @_; |
| 100 | my $r = Catacomb::GF::Reduce->new($p); |
| 101 | $g = $r->reduce($g); |
| 102 | return $r->exp($g, $x); |
| 103 | } |
| 104 | |
| 105 | sub modinv { |
| 106 | croak("Usage: Catacomb::GF::modinv(p, g)") unless @_ == 3; |
| 107 | my ($g, undef, $i) = gcd($_[0], $_[1]); |
| 108 | croak("Arguments aren't coprime in Catacomb::GF::modinv") unless $g == 1; |
| 109 | return $i; |
| 110 | } |
| 111 | |
| 112 | #----- That's all, folks ---------------------------------------------------- |