fcd15e0b |
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 | |
bfdf19cb |
36 | sub mp { new(Catacomb::MP, @_); } |
fcd15e0b |
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]); } |
bfdf19cb |
41 | sub mp_fromstring { fromstring(Catacomb::MP, @_); } |
fcd15e0b |
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; |