fcd15e0b |
1 | =head1 NAME |
2 | |
3 | Catacomb::MP::Prime - prime number generation |
4 | |
5 | =head1 SYNOPSIS |
6 | |
7 | use Catacomb qw(:const :mp :random :pgen); |
8 | |
9 | $p = newprime($nbits, [$rng]); |
10 | |
11 | $filt = Catacomb::MP::Prime::Filter->new($x); |
12 | $filt = $x->filter(); |
13 | $rc = $filt->status(); |
14 | $x = $filt->m(); |
15 | $rc = $filt->step($n); |
16 | $rc = $filt->jump($jfilt); |
17 | $newfilt = $filt->muladd($mul, $add); # integers |
18 | |
19 | $stepper = Catacomb::MP::Prime::Filter->stepper($step); # integer |
20 | $stepper = filterstepper($step); |
21 | $jumper = Catacomb::MP::Prime::Filter->stepper($jump); # MP |
22 | $jumper = filterjumper($jump); |
23 | |
24 | $rabin = Catacomb::MP::Prime::Rabin->new($m); |
25 | $rabin = $p->rabin(); |
26 | $m = $rabin->m(); |
27 | $rc = $rabin->test($wit); |
28 | $n = $rabin->iters(); |
29 | $n = Catacomb::MP::Prime::Rabin->ntests($bits); |
30 | $tester = Catacomb::MP::Prime::Rabin->tester(); |
31 | $tester = $rabintester; |
32 | |
33 | $events = Catacomb::MP::Prime::Gen::Proc->ev(); |
34 | $events = Catacomb::MP::Prime::Gen::Proc->evspin(); |
35 | $events = Catacomb::MP::Prime::Gen::Proc->subev(); |
36 | |
37 | $p = Catacomb::MP::Prime->gen |
38 | ($name, $x, $nsteps, $stepper, $ntests, $tester, [$events]); |
39 | $p = primegen |
40 | ($name, $x, $nsteps, $stepper, $ntests, $tester, [$events]); |
41 | if (($x, $j) = Catacomb::MP::Prime->strongprime_setup |
42 | ($name, $nbits, [$rng], [$nsteps], [$subevents])) { |
43 | $p = Catacomb::MP::Prime->gen |
44 | ($name, $x, $nsteps, $j, $ntests, $tester, [$events]); |
45 | } |
46 | ($p, @f) = Catacomb::MP::Prime->limlee |
47 | ($name, $qbits, $pbits, [$rng], [$on], [$oev], [$iev]); |
48 | ($p, @f) = limleegen |
49 | ($name, $qbits, $pbits, [$rng], [$on], [$oev], [$iev]); |
50 | |
51 | package MyPrimeGenObject; |
52 | sub new { ... }; |
53 | sub BEGIN { ... }; |
54 | sub TRY { ... }; |
55 | sub FAIL { ... }; |
56 | sub PASS { ... }; |
57 | sub DONE { ... }; |
58 | sub ABORT { ... }; |
59 | $name = $ev->name(); |
60 | $x = $ev->m([$xx]); |
61 | $rng = $ev->rand(); |
62 | |
63 | =head1 DESCRIPTION |
64 | |
65 | The B<Catacomb::MP::Prime> and related packages provide a framework for |
66 | generating prime numbers of various special forms. Read Catacomb::MP(3) |
67 | for more information about Catacomb's multiprecision integer support. |
68 | |
69 | =head2 Simple functions |
70 | |
71 | =over |
72 | |
73 | =item B<newprime(>I<nbits>B<,> [I<rng>]B<)> |
74 | |
75 | Returns a random prime between 2^I<nbits> and 2^(I<nbits>+1) (unless |
76 | you're very unlucky). Here, I<rng> must be a random number generator |
77 | object: see Catacomb::Crypto(3). |
78 | |
79 | =back |
80 | |
81 | =head2 Result codes |
82 | |
83 | The following result codes are used by various of the prime-number |
84 | generation functions. They may be imported using the B<:consts> tag. |
85 | |
86 | =over |
87 | |
88 | =item B<PGEN_BEGIN> |
89 | |
90 | About to test a new candidate prime discovered by filtering. This |
91 | shouldn't be returned by functions, but it is used as part of the |
92 | event-handling system. |
93 | |
94 | =item B<PGEN_TRY> |
95 | |
96 | A new candidate has been found by a filter, but has not yet passed a |
97 | primality test. |
98 | |
99 | =item B<PGEN_FAIL> |
100 | |
101 | The number is definitely composite. |
102 | |
103 | =item B<PGEN_PASS> |
104 | |
105 | The number has passed at least one primality test, and is therefore |
106 | likely to be prime. |
107 | |
108 | =item B<PGEN_DONE> |
109 | |
110 | The number is definitely prime. |
111 | |
112 | =item B<PGEN_ABORT> |
113 | |
114 | The search for a prime number has been aborted. |
115 | |
116 | =back |
117 | |
118 | =head2 Filtering for small primes |
119 | |
120 | The class B<Catacomb::MP::Prime::Filter> implements a relatively |
121 | efficient technique for finding numbers with no small factors. |
122 | |
123 | =over |
124 | |
125 | =item I<m>B<-E<gt>smallfactor()> |
126 | |
127 | Returns B<PGEN_DONE> if I<m> is definitely prime (and therefore fairly |
128 | small), B<PGEN_FAIL> if it has some small factor, or B<PGEN_TRY> if it |
129 | has no small factors but might be composite anyway. |
130 | |
131 | =item B<Catacomb::MP::Prime::Filter-E<gt>new(>I<m>B<)> |
132 | |
133 | =item I<m>B<-E<gt>filter()> |
134 | |
135 | Returns a new small-primes filter, initially looking at the number |
136 | I<m>. |
137 | |
138 | =item I<filt>B<-E<gt>m()> |
139 | |
140 | Returns the current number I<m> in the filter. |
141 | |
142 | =item I<filt>B<-E<gt>status()> |
143 | |
144 | Returns the state (a B<PGEN> code) for the current number I<m> in the |
145 | filter. This will usually be B<PGEN_FAIL> if I<m> has a small factor, |
146 | or B<PGEN_TRY> if not; though B<PGEN_PASS> is also possible if I<m> is |
147 | small enough. |
148 | |
149 | =item I<filt>B<-E<gt>step(>I<n>B<)> |
150 | |
151 | Advances the number in the filter by a small step I<n>, returning |
152 | the new status. |
153 | |
154 | =item I<filt>B<-E<gt>jump(>I<jfilt>B<)> |
155 | |
156 | Advances the number in the filter by a large jump, as represented by |
157 | another filter I<jfilt>. This is useful for finding a prime which has |
158 | the form I<n> I<q> + I<k> for some other prime I<q> -- store 2 I<q> in |
159 | a filter and use it as a jump to search for another prime. |
160 | |
161 | =item I<filt>B<-E<gt>muladd(>I<mul>B<,> I<add>B<)> |
162 | |
163 | Returns a new filter whose number is I<m> I<mul> + I<add>. |
164 | |
165 | =back |
166 | |
167 | =head2 Miller-Rabin primality tests |
168 | |
169 | Catacomb's main primality test is the Miller-Rabin test. It is a |
170 | probabilistic test, with a 1/4 probability that any particular test will |
171 | fail to recognize a given number as being composite. However, it is |
172 | important to observe that this is not the same as the probability that a |
173 | random number is composite given that it passed a test -- this latter is |
174 | much smaller. |
175 | |
176 | =over |
177 | |
178 | =item B<Catacomb::MP::Prime::Rabin-E<gt>new(>I<m>B<)> |
179 | |
180 | =item I<m>B<-E<gt>rabin()> |
181 | |
182 | Constructs a new Rabin-Miller testing context for the purpose of testing |
183 | the candidate I<m>. Returns B<undef> if I<m> is negative or even. |
184 | |
185 | =item I<rabin>B<-E<gt>m()> |
186 | |
187 | Returns the integer under test in the given context. |
188 | |
189 | =item I<rabin>B<-E<gt>test(>I<wit>B<)> |
190 | |
191 | Tests I<m> with witness I<wit>. Returns B<PGEN_FAIL> or B<PGEN_PASS>. |
192 | The witness should usually be chosen randomly. |
193 | |
194 | =item I<rabin>B<-E<gt>iters()> |
195 | |
196 | Returns the recommended number of tests for the candidate under test, |
197 | assuming that we came across the candidate at random. |
198 | |
199 | =item B<Catacomb::MP::Prime::Rabin-E<gt>ntests(>I<bits>B<)> |
200 | |
201 | Returns the recommended number of tests for a candidate which is |
202 | I<nbits> bits long, assuming that we came across the candidate at |
203 | random. |
204 | |
205 | =back |
206 | |
207 | =head2 Prime generation concepts |
208 | |
209 | The prime generator is based on the concepts of I<steppers>, I<filters> |
210 | and I<event handlers>. |
211 | |
212 | =over |
213 | |
214 | =item * |
215 | |
216 | Steppers are responsible for producing candidate primes, and (usually) |
217 | testing them for small factors (e.g., using B<smallfactor()>). A |
218 | stepper is expected to be relatively fast, and leave the heavy lifting |
219 | to testers. |
220 | |
221 | =item * |
222 | |
223 | Testers are responsible for applying primality tests to candidates. |
224 | |
225 | =item * |
226 | |
227 | Event handlers report interesting events during prime generation, to |
228 | maintain a progress display or similar. |
229 | |
230 | =back |
231 | |
232 | These various kinds of objects all have essentially the same interface, |
233 | which is built from I<events>. An event contains all the useful |
234 | information about the current progress of a prime generation task. |
235 | Events are objects of type B<Catacomb::MP::Prime::Gen::Event>, though |
236 | fortunately one rarely needs to type this. Event objects can't be |
237 | created by Perl code. |
238 | |
239 | =over |
240 | |
241 | =item I<ev>B<-E<gt>name()> |
242 | |
243 | Returns the name of the prime being generated. |
244 | |
245 | =item I<ev>B<-E<gt>m(>[I<x>]B<)> |
246 | |
247 | Returns the current candidate prime. If I<x> is supplied then it |
248 | sets a new candidate prime. This is used by the stepper interface. |
249 | |
250 | =item I<ev>B<-E<gt>steps()> |
251 | |
252 | Returns the number of steps remaining before the generation task fails. |
253 | |
254 | =item I<ev>B<-E<gt>tests()> |
255 | |
256 | Returns the name of tests remaining before the generation task succeeds. |
257 | |
258 | =item I<ev>B<-E<gt>rand()> |
259 | |
260 | Returns a pseudorandom number generator which is likely to be fast but |
261 | not cryptographically strong. |
262 | |
263 | =back |
264 | |
265 | =head2 Built-in steppers and testers |
266 | |
267 | =over |
268 | |
269 | =item B<Catacomb::MP::Prime::Filter-E<gt>stepper(>I<step>B<)> |
270 | |
271 | =item B<filterstepper(>I<step>B<)> |
272 | |
273 | Returns a stepper object which steps on by I<step> (a small Perl |
274 | integer) until it finds a number with no small prime factors. |
275 | |
276 | =item B<Catacomb::MP::Prime::Filter-E<gt>jumper(>I<jump>B<)> |
277 | |
278 | =item I<jump>B<-E<gt>jumper()> |
279 | |
280 | Returns a jumper object which jumps on by I<jump> (a large |
281 | multiprecision integer) until it finds a number with no small prime |
282 | factors. |
283 | |
284 | =item B<Catacomb::MP::Prime::Rabin-E<gt>tester()> |
285 | |
286 | Returns a tester object which applies an iteration of the Miller-Rabin |
287 | probabilistic primality test. In fact, there only needs to be one of |
288 | these, so it's called B<$rabintester>. |
289 | |
290 | =item B<Catacomb::MP::Prime::Gen::Proc-E<gt>ev()> |
291 | |
292 | A standard event handler which prints the name of the prime being |
293 | generated and a string of C<.> and C<+> signs for failures and |
294 | successes, such as is relatively commonplace. In fact, there only needs |
295 | to be one of these, so it's called B<$pg_events>. |
296 | |
297 | =item B<Catacomb::MP::Prime::Gen::Proc-E<gt>evspin()> |
298 | |
299 | An event handler which shows a spinning baton while it works. This is |
300 | mainly used as the subsidiary event handler when generating Lim-Lee |
301 | primes. There only needs to be one of these, so it's called |
302 | B<$pg_evspin>. |
303 | |
304 | =item B<Catacomb::MP::Prime::Gen::Proc-E<gt>subev()> |
305 | |
306 | An event handler which works like B<ev()> above, but puts square |
307 | brackets around its output. Also suitable for use in Lim-Lee |
308 | generation. There only needs to be one of these, so it's called |
309 | B<$pg_subev>. |
310 | |
311 | =back |
312 | |
313 | =head2 Prime generation |
314 | |
315 | Prime generation is driven by the procedure |
316 | B<Catacomb::MP::Prime-E<gt>gen()>, which is also named B<primegen()> for |
317 | convenience. |
318 | |
319 | =over |
320 | |
321 | =item B<Catacomb::MP::Prime-E<gt>gen(>I<name>B<,> I<m>B<,> I<nsteps>B<,> I<stepper>B<,> I<ntests>B<,> I<tester>B<,> [I<events>]B<)> |
322 | |
323 | =item B<primegen(>I<name>B<,> I<m>B<,> I<nsteps>B<,> I<stepper>B<,> I<ntests>B<,> I<tester>B<,> [I<events>]B<)> |
324 | |
325 | Generates a prime number. It will start with the integer I<m>, and run |
326 | the I<stepper> for at most I<nsteps> times (infinitely if I<nsteps> is |
327 | zero), returning B<undef> if it fails. Each time the stepper reports a |
328 | plausible candidate, it runs the tester up to I<ntests> times; it |
329 | returns the candidate if all these tests succeeded. It will call the |
330 | event handler after each step and test. |
331 | |
332 | =back |
333 | |
334 | =head2 Writing your own steppers, testers and event handlers |
335 | |
336 | As mentioned, steppers, testers and event handlers have similar |
337 | interfaces. Each is represented by an object whose class is a |
338 | descendent (via B<@ISA>) of B<Catacomb::MP::Prime::Gen::Proc>. The |
339 | prime generator will call methods on your object as required. |
340 | |
341 | Event handlers are the easiest, so we deal with them first. All methods |
342 | are called with one argument which is the event object. The methods |
343 | called are as follows. |
344 | |
345 | =over |
346 | |
347 | =item B<PG_BEGIN> |
348 | |
349 | Prime generation has begun. |
350 | |
351 | =item B<PG_TRY> |
352 | |
353 | About to start testing a new number. |
354 | |
355 | =item B<PG_PASS> |
356 | |
357 | Number passed a primality test. |
358 | |
359 | =item B<PG_FAIL> |
360 | |
361 | Number failed a primality test. |
362 | |
363 | =item B<PG_DONE> |
364 | |
365 | Prime number found successfully. |
366 | |
367 | =item B<PG_ABORT> |
368 | |
369 | No prime number found; we gave up. |
370 | |
371 | =back |
372 | |
373 | Any of these methods may return B<PGEN_ABORT> (-1) to abandon prime |
374 | searching. This is intended to be used, for example, by a progress |
375 | dialogue box if its cancel button is pressed. Any other value is |
376 | ignored. |
377 | |
378 | Here's a simple example of an event handler. |
379 | |
380 | package Strange::Events; |
381 | @ISA = qw(Catacomb::MP::Prime::Gen::Proc); |
382 | |
383 | sub new { bless {}, $_[0]; } |
384 | |
385 | sub PG_BEGIN { |
386 | my ($me, $ev) = @_; |
387 | local $| = 1; |
388 | print $ev->name(), " ["; |
389 | } |
390 | |
391 | sub PG_PASS { local $| = 1; print "*"; } |
392 | sub PG_FAIL { local $| = 1; print "."; } |
393 | sub PG_ABORT { local $| = 1; print "] :-(\n"; } |
394 | sub PG_DONE { local $| = 1; print "]\n"; } |
395 | |
396 | Steppers use fewer methods, but are a bit more involved. |
397 | |
398 | =over |
399 | |
400 | =item B<PG_BEGIN> |
401 | |
402 | Initialize the stepper. Read the starting point from the event, or |
403 | store a new starting point, as appropriate. Return B<PGEN_DONE> if the |
404 | starting point is satisfactory, B<PGEN_ABORT> for failure, or B<PGEN_TRY> |
405 | to run the tester. |
406 | |
407 | =item B<PG_TRY> |
408 | |
409 | Advance the stepper. Write the new number to the event. Return as for |
410 | B<PG_BEGIN>. |
411 | |
412 | =item B<PG_DONE> |
413 | |
414 | All is over. Tidy up. |
415 | |
416 | =back |
417 | |
418 | Testers are similar. |
419 | |
420 | =over |
421 | |
422 | =item B<PG_BEGIN> |
423 | |
424 | Initialize the tester. Read the starting point from the event. Return |
425 | B<PGEN_DONE> if the starting point is satisfactory, B<PGEN_PASS> if |
426 | you've actually run a successful test, B<PGEN_FAIL> to reject the |
427 | candidate, or B<PGEN_TRY> to proceed to testing. |
428 | |
429 | =item B<PG_TRY> |
430 | |
431 | Run a test. Return B<PGEN_DONE> if the number is satisfactory, |
432 | B<PGEN_PASS> if it passed a test, or B<PGEN_FAIL> if it failed. |
433 | |
434 | =item B<PG_DONE> |
435 | |
436 | Testing is done. Tidy up. |
437 | |
438 | =back |
439 | |
440 | Finally, any method can return B<PGEN_ABORT> to stop prime generation in |
441 | its tracks almost immediately. (The B<PG_DONE> methods are still called |
442 | for the stepper, and for the tester if it's active.) |
443 | |
444 | It's probably best to do tidying in B<PG_DONE> rather than leaving it |
445 | until B<DESTROY>, since testers and steppers and things may get left |
446 | around for a while, espectially if they're simple. |
447 | |
448 | Since steppers and testers often work together, here's an example of a |
449 | pair for generating I<Sophie Germain primes>. A prime number I<q> is |
450 | Sophie-Germain prime if 2 I<q> + 1 is also prime. We work by |
451 | maintaining separate filters and testing contexts for I<q> and 2 I<q> + |
452 | 1, and checking both in parallel. Generating Sophie Germain primes is a |
453 | long job. |
454 | |
455 | package SophieGermain::Stepper; |
456 | use Catacomb qw(:const :mp :pgen); |
457 | @ISA = qw(Catacomb::MP::Prime::Gen::Proc); |
458 | |
459 | sub new { bless [undef, undef], $_[0]; } |
460 | |
461 | sub _step { |
462 | my ($me, $ev) = @_; |
463 | while ($me->[0]->status() == PGEN_FAIL || |
464 | $me->[1]->status() == PGEN_FAIL) { |
465 | $me->[0]->step(2); |
466 | $me->[1]->step(4); |
467 | } |
468 | $ev->m($me->[0]->m()); |
469 | return PGEN_TRY; |
470 | } |
471 | |
472 | sub PG_BEGIN { |
473 | my ($me, $ev) = @_; |
474 | my $x = $ev->m(); |
475 | $me->[0] = $x->filter(); |
476 | $me->[1] = (2*$x + 1)->filter(); |
477 | _step($me, $ev); |
478 | } |
479 | |
480 | sub PG_TRY { |
481 | my ($me, $ev) = @_; |
482 | $me->[0]->step(2); |
483 | $me->[1]->step(4); |
484 | _step($me, $ev); |
485 | } |
486 | |
487 | sub PG_DONE { |
488 | my ($me, $ev) = @_; |
489 | $me->[0] = $me->[1] = undef; |
490 | } |
491 | |
492 | package SophieGermain::Tester; |
493 | use Catacomb qw(:const :mp :pgen); |
494 | @ISA = qw(Catacomb::MP::Prime::Gen::Proc); |
495 | |
496 | sub new { bless [undef, undef], $_[0]; } |
497 | |
498 | sub PG_BEGIN { |
499 | my ($me, $ev) = @_; |
500 | my $x = $ev->m(); |
501 | $me->[0] = $x->rabin(); |
502 | $me->[1] = (2*$x + 1)->rabin(); |
503 | return PGEN_TRY; |
504 | } |
505 | |
506 | sub _test { |
507 | my ($r, $rabin) = @_; |
508 | my $w = $r->mprange($rabin->m()); |
509 | return $rabin->test($w) == PGEN_PASS; |
510 | } |
511 | |
512 | sub PG_TRY { |
513 | my ($me, $ev) = @_; |
514 | my $r = $ev->rand(); |
fcd15e0b |
515 | return _test($r, $me->[0]) && _test($r, $me->[1]) ? |
516 | PGEN_PASS : PGEN_FAIL; |
517 | } |
518 | |
519 | sub PG_DONE { |
520 | my ($me, $ev) = @_; |
521 | $me->[0] = $me->[1] = undef; |
522 | } |
523 | |