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

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