| 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, @_); } |
| 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, @_); } |
| 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 { ¬2c($_[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; |