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

   1 # -*-perl-*-
   2 #
   3 # $Id$
   4 #
   5 # Catacomb multiprecision integer interface
   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 #----- Multiprecision arithmetic --------------------------------------------
  29
  30 package Catacomb::MP;
  31 use Catacomb::Base;
  32 use Catacomb::Rand;
  33 use Catacomb::Field;
  34 use Carp;
  35
  36 sub mp { new(Catacomb::MP, $_[0]); }
  37 sub mp_loadb { loadb(Catacomb::MP, $_[0]); }
  38 sub mp_loadl { loadl(Catacomb::MP, $_[0]); }
  39 sub mp_loadb2c { loadb2c(Catacomb::MP, $_[0]); }
  40 sub mp_loadl2c { loadl2c(Catacomb::MP, $_[0]); }
  41 sub mp_fromstring { fromstring(Catacomb::MP, $_[0]); }
  42
  43 sub mod { (&div($_[0], $_[1]))[1]; }
  44
  45 sub _binop {
  46   my ($func, $a, $b, $flag) = @_;
  47   return $flag ? &$func($b, $a) : &$func($a, $b);
  48 }
  49
  50 sub _mul {
  51   my ($a, $b, $flag) = @_;
  52   if (UNIVERSAL::isa($b, Catacomb::EC::Pt)) {
  53     return $b->mul($a);
  54   }
  55   mul($a, $b);
  56 }
  57
  58 use overload
  59   '+' => sub { _binop(\&add, @_); },
  60   '-' => sub { _binop(\&sub, @_); },
  61   '*' => \&_mul,
  62   '/' => sub { _binop(\&div, @_); },
  63   '%' => sub { _binop(\&mod, @_); },
  64   '&' => sub { _binop(\&and2c, @_); },
  65   '|' => sub { _binop(\&or2c, @_); },
  66   '^' => sub { _binop(\&xor2c, @_); },
  67   '**' => sub { _binop(\&exp, @_); },
  68   '>>' => sub { &lsr2c(@_[0, 1]); },
  69   '<<' => sub { &lsl2c(@_[0, 1]); },
  70   '~' => sub { &not2c($_[0]) },
  71   '==' => sub { _binop(\&eq, @_); },
  72   'eq' => sub { _binop(\&eq, @_); },
  73   '<=>' => sub { _binop(\&cmp, @_); },
  74   'cmp' => sub { _binop(\&cmp, @_); },
  75   '""' => sub { &tostring($_[0]); },,
  76   '0+' => sub { &toint($_[0]); },
  77   'sqrt' => sub { &sqrt($_[0]); },
  78   'neg' => sub { &neg($_[0]); };
  79
  80 sub import {
  81   my ($me, @imp) = @_;
  82   for my $i (@imp) {
  83     if ($i eq ":constant") {
  84       overload::constant integer => sub { new(undef, $_[0]); };
  85     } else {
  86       croak("unknown import for Catacomb::MP: `$i'");
  87     }
  88   }
  89 }
  90
  91 sub modexp {
  92   croak("Usage: Catacomb::MP::modexp(p, g, x)") unless @_ == 3;
  93   my ($p, $g, $x) = @_;
  94   $g = $p - $g if $g < 0;
  95   $g = $g % $p if $g > $p;
  96   if ($p & 1) {
  97     my $mm = $p->mont();
  98     return $mm->exp($g, $x);
  99   } else {
 100     my $mb = $p->barrett();
 101     return $mb->exp($g, $x);
 102   }
 103 }
 104
 105 sub primefield {
 106   croak("Usage: Catacomb::MP::primefield(p)") unless @_ == 1;
 107   return Catacomb::Field->prime($_[0]);
 108 }
 109
 110 sub niceprimefield {
 111   croak("Usage: Catacomb::MP::niceprimefield(p)") unless @_ == 1;
 112   return Catacomb::Field->niceprime($_[0]);
 113 }
 114
 115 sub primegroup {
 116   croak("Usage: Catacomb::MP::primegroup(p, g, q)") unless @_ == 3;
 117   return Catacomb::Group->prime(@_);
 118 }
 119
 120 sub filter {
 121   croak("Usage: Catacomb::MP::filter(p)") unless @_ == 1;
 122   return Catacomb::MP::Prime::Filter->new($_[0]);
 123 }
 124
 125 sub modinv {
 126   croak("Usage: Catacomb::MP::modinv(p, x)") unless @_ == 2;
 127   my ($g, undef, $i) = gcd($_[0], $_[1]);
 128   croak("Arguments aren't coprime in Catacomb::MP::modinv") unless $g == 1;
 129   return $i;
 130 }
 131
 132 sub jac {
 133   # Reverse arguments for object-oriented syntax.
 134   croak("Usage: Catacomb::MP::jac(n, a)") unless @_ == 2;
 135   jacobi($_[1], $_[0]);
 136 }
 137
 138 sub mont {
 139   croak("Usage: Catacomb::MP::mont(x)") unless @_ == 1;
 140   return Catacomb::MP::Mont->new($_[0]);
 141 }
 142
 143 sub barrett {
 144   croak("Usage: Catacomb::MP::barrett(x)") unless @_ == 1;
 145   return Catacomb::MP::Mont->new($_[0]);
 146 }
 147
 148 sub mkreduce {
 149   croak("Usage: Catacomb::MP::mkreduce(x)") unless @_ == 1;
 150   return Catacomb::MP::Reduce->new($_[0]);
 151 }
 152
 153 sub rabin {
 154   croak("Usage: Catacomb::MP::rabin(x)") unless @_ == 1;
 155   return Catacomb::MP::Prime::Rabin->new($_[0]);
 156 }
 157
 158 sub newprime {
 159   croak("Usage: Catacomb::MP::newprime(nbits, [rng]")
 160     unless @_ >= 1 && @_ <= 2;
 161   my ($nbits, $rng) = @_;
 162   $rng ||= $Catacomb::random;
 163   return Catacomb::MP::Prime->gen
 164     ("p", $rng->mp($nbits, 1), 0,
 165      Catacomb::MP::Prime::Filter->stepper(2),
 166      Catacomb::MP::Prime::Rabin->ntests($nbits),
 167      Catacomb::MP::Prime::Rabin->tester());
 168 }
 169
 170 sub jumper {
 171   croak("Usage: Catacomb::MP::jumper(p)") unless @_ == 1;
 172   return Catacomb::MP::Prime::Filter->jumper($_[0]);
 173 }
 174
 175 package Catacomb::MP::Mont;
 176
 177 *out = \&reduce;
 178
 179 package Catacomb::MP::Prime::Filter;
 180
 181 package Catacomb::MP::Prime::Filter;
 182
 183 sub filterstepper { &stepper(Catacomb::MP::Prime::Filter, @_); }
 184 sub filterjumper { &jumper(Catacomb::MP::Prime::Filter, @_); }
 185
 186 package Catacomb::MP::Prime;
 187
 188 sub primegen { &gen(Catacomb::MP::Prime, @_); }
 189 sub limleegen { &limlee(Catacomb::MP::Prime, @_); }
 190
 191 package Catacomb::MP::Prime::Rabin;
 192
 193 sub rabintester { &tester(Catacomb::MP::Prime::Rabin, @_); }
 194
 195 {
 196   my $cmpg = "Catacomb::MP::Prime::Gen";
 197   foreach my $i (qw(FilterStepper JumpStepper RabinTester)) {
 198     @{"${cmpg}::${i}::ISA"} = ("${cmpg}::MagicProc");
 199   }
 200   @{"${cmpg}::MagicProc::ISA"} = ("${cmpg}::Proc");
 201 }
 202
 203 #----- That's all, folks ----------------------------------------------------
 204
 205 1;