3 Catacomb::MP::Prime - prime number generation
7 use Catacomb qw(:const :mp :random :pgen);
9 $p = newprime($nbits, [$rng]);
11 $filt = Catacomb::MP::Prime::Filter->new($x);
13 $rc = $filt->status();
15 $rc = $filt->step($n);
16 $rc = $filt->jump($jfilt);
17 $newfilt = $filt->muladd($mul, $add); # integers
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);
24 $rabin = Catacomb::MP::Prime::Rabin->new($m);
27 $rc = $rabin->test($wit);
29 $n = Catacomb::MP::Prime::Rabin->ntests($bits);
30 $tester = Catacomb::MP::Prime::Rabin->tester();
31 $tester = $rabintester;
33 $events = Catacomb::MP::Prime::Gen::Proc->ev();
34 $events = Catacomb::MP::Prime::Gen::Proc->evspin();
35 $events = Catacomb::MP::Prime::Gen::Proc->subev();
37 $p = Catacomb::MP::Prime->gen
38 ($name, $x, $nsteps, $stepper, $ntests, $tester, [$events]);
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]);
46 ($p, @f) = Catacomb::MP::Prime->limlee
47 ($name, $qbits, $pbits, [$rng], [$on], [$oev], [$iev]);
49 ($name, $qbits, $pbits, [$rng], [$on], [$oev], [$iev]);
51 package MyPrimeGenObject;
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.
69 =head2 Simple functions
73 =item B<newprime(>I<nbits>B<,> [I<rng>]B<)>
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).
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.
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.
96 A new candidate has been found by a filter, but has not yet passed a
101 The number is definitely composite.
105 The number has passed at least one primality test, and is therefore
110 The number is definitely prime.
114 The search for a prime number has been aborted.
118 =head2 Filtering for small primes
120 The class B<Catacomb::MP::Prime::Filter> implements a relatively
121 efficient technique for finding numbers with no small factors.
125 =item I<m>B<-E<gt>smallfactor()>
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.
131 =item B<Catacomb::MP::Prime::Filter-E<gt>new(>I<m>B<)>
133 =item I<m>B<-E<gt>filter()>
135 Returns a new small-primes filter, initially looking at the number
138 =item I<filt>B<-E<gt>m()>
140 Returns the current number I<m> in the filter.
142 =item I<filt>B<-E<gt>status()>
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
149 =item I<filt>B<-E<gt>step(>I<n>B<)>
151 Advances the number in the filter by a small step I<n>, returning
154 =item I<filt>B<-E<gt>jump(>I<jfilt>B<)>
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.
161 =item I<filt>B<-E<gt>muladd(>I<mul>B<,> I<add>B<)>
163 Returns a new filter whose number is I<m> I<mul> + I<add>.
167 =head2 Miller-Rabin primality tests
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
178 =item B<Catacomb::MP::Prime::Rabin-E<gt>new(>I<m>B<)>
180 =item I<m>B<-E<gt>rabin()>
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.
185 =item I<rabin>B<-E<gt>m()>
187 Returns the integer under test in the given context.
189 =item I<rabin>B<-E<gt>test(>I<wit>B<)>
191 Tests I<m> with witness I<wit>. Returns B<PGEN_FAIL> or B<PGEN_PASS>.
192 The witness should usually be chosen randomly.
194 =item I<rabin>B<-E<gt>iters()>
196 Returns the recommended number of tests for the candidate under test,
197 assuming that we came across the candidate at random.
199 =item B<Catacomb::MP::Prime::Rabin-E<gt>ntests(>I<bits>B<)>
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
207 =head2 Prime generation concepts
209 The prime generator is based on the concepts of I<steppers>, I<filters>
210 and I<event handlers>.
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
223 Testers are responsible for applying primality tests to candidates.
227 Event handlers report interesting events during prime generation, to
228 maintain a progress display or similar.
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.
241 =item I<ev>B<-E<gt>name()>
243 Returns the name of the prime being generated.
245 =item I<ev>B<-E<gt>m(>[I<x>]B<)>
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.
250 =item I<ev>B<-E<gt>steps()>
252 Returns the number of steps remaining before the generation task fails.
254 =item I<ev>B<-E<gt>tests()>
256 Returns the name of tests remaining before the generation task succeeds.
258 =item I<ev>B<-E<gt>rand()>
260 Returns a pseudorandom number generator which is likely to be fast but
261 not cryptographically strong.
265 =head2 Built-in steppers and testers
269 =item B<Catacomb::MP::Prime::Filter-E<gt>stepper(>I<step>B<)>
271 =item B<filterstepper(>I<step>B<)>
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.
276 =item B<Catacomb::MP::Prime::Filter-E<gt>jumper(>I<jump>B<)>
278 =item I<jump>B<-E<gt>jumper()>
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
284 =item B<Catacomb::MP::Prime::Rabin-E<gt>tester()>
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>.
290 =item B<Catacomb::MP::Prime::Gen::Proc-E<gt>ev()>
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>.
297 =item B<Catacomb::MP::Prime::Gen::Proc-E<gt>evspin()>
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
304 =item B<Catacomb::MP::Prime::Gen::Proc-E<gt>subev()>
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
313 =head2 Prime generation
315 Prime generation is driven by the procedure
316 B<Catacomb::MP::Prime-E<gt>gen()>, which is also named B<primegen()> for
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<)>
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<)>
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.
334 =head2 Writing your own steppers, testers and event handlers
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.
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.
349 Prime generation has begun.
353 About to start testing a new number.
357 Number passed a primality test.
361 Number failed a primality test.
365 Prime number found successfully.
369 No prime number found; we gave up.
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
378 Here's a simple example of an event handler.
380 package Strange::Events;
381 @ISA = qw(Catacomb::MP::Prime::Gen::Proc);
383 sub new { bless {}, $_[0]; }
388 print $ev->name(), " [";
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"; }
396 Steppers use fewer methods, but are a bit more involved.
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>
409 Advance the stepper. Write the new number to the event. Return as for
414 All is over. Tidy up.
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.
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.
436 Testing is done. Tidy up.
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.)
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.
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
455 package SophieGermain::Stepper;
456 use Catacomb qw(:const :mp :pgen);
457 @ISA = qw(Catacomb::MP::Prime::Gen::Proc);
459 sub new { bless [undef, undef], $_[0]; }
463 while ($me->[0]->status() == PGEN_FAIL ||
464 $me->[1]->status() == PGEN_FAIL) {
468 $ev->m($me->[0]->m());
475 $me->[0] = $x->filter();
476 $me->[1] = (2*$x + 1)->filter();
489 $me->[0] = $me->[1] = undef;
492 package SophieGermain::Tester;
493 use Catacomb qw(:const :mp :pgen);
494 @ISA = qw(Catacomb::MP::Prime::Gen::Proc);
496 sub new { bless [undef, undef], $_[0]; }
501 $me->[0] = $x->rabin();
502 $me->[1] = (2*$x + 1)->rabin();
507 my ($r, $rabin) = @_;
508 my $w = $r->mprange($rabin->m());
509 return $rabin->test($w) == PGEN_PASS;
515 return _test($r, $me->[0]) && _test($r, $me->[1]) ?
516 PGEN_PASS : PGEN_FAIL;
521 $me->[0] = $me->[1] = undef;