--- /dev/null
+=head1 NAME
+
+Catacomb::MP::Prime - prime number generation
+
+=head1 SYNOPSIS
+
+ use Catacomb qw(:const :mp :random :pgen);
+
+ $p = newprime($nbits, [$rng]);
+
+ $filt = Catacomb::MP::Prime::Filter->new($x);
+ $filt = $x->filter();
+ $rc = $filt->status();
+ $x = $filt->m();
+ $rc = $filt->step($n);
+ $rc = $filt->jump($jfilt);
+ $newfilt = $filt->muladd($mul, $add); # integers
+
+ $stepper = Catacomb::MP::Prime::Filter->stepper($step); # integer
+ $stepper = filterstepper($step);
+ $jumper = Catacomb::MP::Prime::Filter->stepper($jump); # MP
+ $jumper = filterjumper($jump);
+
+ $rabin = Catacomb::MP::Prime::Rabin->new($m);
+ $rabin = $p->rabin();
+ $m = $rabin->m();
+ $rc = $rabin->test($wit);
+ $n = $rabin->iters();
+ $n = Catacomb::MP::Prime::Rabin->ntests($bits);
+ $tester = Catacomb::MP::Prime::Rabin->tester();
+ $tester = $rabintester;
+
+ $events = Catacomb::MP::Prime::Gen::Proc->ev();
+ $events = Catacomb::MP::Prime::Gen::Proc->evspin();
+ $events = Catacomb::MP::Prime::Gen::Proc->subev();
+
+ $p = Catacomb::MP::Prime->gen
+ ($name, $x, $nsteps, $stepper, $ntests, $tester, [$events]);
+ $p = primegen
+ ($name, $x, $nsteps, $stepper, $ntests, $tester, [$events]);
+ if (($x, $j) = Catacomb::MP::Prime->strongprime_setup
+ ($name, $nbits, [$rng], [$nsteps], [$subevents])) {
+ $p = Catacomb::MP::Prime->gen
+ ($name, $x, $nsteps, $j, $ntests, $tester, [$events]);
+ }
+ ($p, @f) = Catacomb::MP::Prime->limlee
+ ($name, $qbits, $pbits, [$rng], [$on], [$oev], [$iev]);
+ ($p, @f) = limleegen
+ ($name, $qbits, $pbits, [$rng], [$on], [$oev], [$iev]);
+
+ package MyPrimeGenObject;
+ sub new { ... };
+ sub BEGIN { ... };
+ sub TRY { ... };
+ sub FAIL { ... };
+ sub PASS { ... };
+ sub DONE { ... };
+ sub ABORT { ... };
+ $name = $ev->name();
+ $x = $ev->m([$xx]);
+ $rng = $ev->rand();
+
+=head1 DESCRIPTION
+
+The B<Catacomb::MP::Prime> and related packages provide a framework for
+generating prime numbers of various special forms. Read Catacomb::MP(3)
+for more information about Catacomb's multiprecision integer support.
+
+=head2 Simple functions
+
+=over
+
+=item B<newprime(>I<nbits>B<,> [I<rng>]B<)>
+
+Returns a random prime between 2^I<nbits> and 2^(I<nbits>+1) (unless
+you're very unlucky). Here, I<rng> must be a random number generator
+object: see Catacomb::Crypto(3).
+
+=back
+
+=head2 Result codes
+
+The following result codes are used by various of the prime-number
+generation functions. They may be imported using the B<:consts> tag.
+
+=over
+
+=item B<PGEN_BEGIN>
+
+About to test a new candidate prime discovered by filtering. This
+shouldn't be returned by functions, but it is used as part of the
+event-handling system.
+
+=item B<PGEN_TRY>
+
+A new candidate has been found by a filter, but has not yet passed a
+primality test.
+
+=item B<PGEN_FAIL>
+
+The number is definitely composite.
+
+=item B<PGEN_PASS>
+
+The number has passed at least one primality test, and is therefore
+likely to be prime.
+
+=item B<PGEN_DONE>
+
+The number is definitely prime.
+
+=item B<PGEN_ABORT>
+
+The search for a prime number has been aborted.
+
+=back
+
+=head2 Filtering for small primes
+
+The class B<Catacomb::MP::Prime::Filter> implements a relatively
+efficient technique for finding numbers with no small factors.
+
+=over
+
+=item I<m>B<-E<gt>smallfactor()>
+
+Returns B<PGEN_DONE> if I<m> is definitely prime (and therefore fairly
+small), B<PGEN_FAIL> if it has some small factor, or B<PGEN_TRY> if it
+has no small factors but might be composite anyway.
+
+=item B<Catacomb::MP::Prime::Filter-E<gt>new(>I<m>B<)>
+
+=item I<m>B<-E<gt>filter()>
+
+Returns a new small-primes filter, initially looking at the number
+I<m>.
+
+=item I<filt>B<-E<gt>m()>
+
+Returns the current number I<m> in the filter.
+
+=item I<filt>B<-E<gt>status()>
+
+Returns the state (a B<PGEN> code) for the current number I<m> in the
+filter. This will usually be B<PGEN_FAIL> if I<m> has a small factor,
+or B<PGEN_TRY> if not; though B<PGEN_PASS> is also possible if I<m> is
+small enough.
+
+=item I<filt>B<-E<gt>step(>I<n>B<)>
+
+Advances the number in the filter by a small step I<n>, returning
+the new status.
+
+=item I<filt>B<-E<gt>jump(>I<jfilt>B<)>
+
+Advances the number in the filter by a large jump, as represented by
+another filter I<jfilt>. This is useful for finding a prime which has
+the form I<n> I<q> + I<k> for some other prime I<q> -- store 2 I<q> in
+a filter and use it as a jump to search for another prime.
+
+=item I<filt>B<-E<gt>muladd(>I<mul>B<,> I<add>B<)>
+
+Returns a new filter whose number is I<m> I<mul> + I<add>.
+
+=back
+
+=head2 Miller-Rabin primality tests
+
+Catacomb's main primality test is the Miller-Rabin test. It is a
+probabilistic test, with a 1/4 probability that any particular test will
+fail to recognize a given number as being composite. However, it is
+important to observe that this is not the same as the probability that a
+random number is composite given that it passed a test -- this latter is
+much smaller.
+
+=over
+
+=item B<Catacomb::MP::Prime::Rabin-E<gt>new(>I<m>B<)>
+
+=item I<m>B<-E<gt>rabin()>
+
+Constructs a new Rabin-Miller testing context for the purpose of testing
+the candidate I<m>. Returns B<undef> if I<m> is negative or even.
+
+=item I<rabin>B<-E<gt>m()>
+
+Returns the integer under test in the given context.
+
+=item I<rabin>B<-E<gt>test(>I<wit>B<)>
+
+Tests I<m> with witness I<wit>. Returns B<PGEN_FAIL> or B<PGEN_PASS>.
+The witness should usually be chosen randomly.
+
+=item I<rabin>B<-E<gt>iters()>
+
+Returns the recommended number of tests for the candidate under test,
+assuming that we came across the candidate at random.
+
+=item B<Catacomb::MP::Prime::Rabin-E<gt>ntests(>I<bits>B<)>
+
+Returns the recommended number of tests for a candidate which is
+I<nbits> bits long, assuming that we came across the candidate at
+random.
+
+=back
+
+=head2 Prime generation concepts
+
+The prime generator is based on the concepts of I<steppers>, I<filters>
+and I<event handlers>.
+
+=over
+
+=item *
+
+Steppers are responsible for producing candidate primes, and (usually)
+testing them for small factors (e.g., using B<smallfactor()>). A
+stepper is expected to be relatively fast, and leave the heavy lifting
+to testers.
+
+=item *
+
+Testers are responsible for applying primality tests to candidates.
+
+=item *
+
+Event handlers report interesting events during prime generation, to
+maintain a progress display or similar.
+
+=back
+
+These various kinds of objects all have essentially the same interface,
+which is built from I<events>. An event contains all the useful
+information about the current progress of a prime generation task.
+Events are objects of type B<Catacomb::MP::Prime::Gen::Event>, though
+fortunately one rarely needs to type this. Event objects can't be
+created by Perl code.
+
+=over
+
+=item I<ev>B<-E<gt>name()>
+
+Returns the name of the prime being generated.
+
+=item I<ev>B<-E<gt>m(>[I<x>]B<)>
+
+Returns the current candidate prime. If I<x> is supplied then it
+sets a new candidate prime. This is used by the stepper interface.
+
+=item I<ev>B<-E<gt>steps()>
+
+Returns the number of steps remaining before the generation task fails.
+
+=item I<ev>B<-E<gt>tests()>
+
+Returns the name of tests remaining before the generation task succeeds.
+
+=item I<ev>B<-E<gt>rand()>
+
+Returns a pseudorandom number generator which is likely to be fast but
+not cryptographically strong.
+
+=back
+
+=head2 Built-in steppers and testers
+
+=over
+
+=item B<Catacomb::MP::Prime::Filter-E<gt>stepper(>I<step>B<)>
+
+=item B<filterstepper(>I<step>B<)>
+
+Returns a stepper object which steps on by I<step> (a small Perl
+integer) until it finds a number with no small prime factors.
+
+=item B<Catacomb::MP::Prime::Filter-E<gt>jumper(>I<jump>B<)>
+
+=item I<jump>B<-E<gt>jumper()>
+
+Returns a jumper object which jumps on by I<jump> (a large
+multiprecision integer) until it finds a number with no small prime
+factors.
+
+=item B<Catacomb::MP::Prime::Rabin-E<gt>tester()>
+
+Returns a tester object which applies an iteration of the Miller-Rabin
+probabilistic primality test. In fact, there only needs to be one of
+these, so it's called B<$rabintester>.
+
+=item B<Catacomb::MP::Prime::Gen::Proc-E<gt>ev()>
+
+A standard event handler which prints the name of the prime being
+generated and a string of C<.> and C<+> signs for failures and
+successes, such as is relatively commonplace. In fact, there only needs
+to be one of these, so it's called B<$pg_events>.
+
+=item B<Catacomb::MP::Prime::Gen::Proc-E<gt>evspin()>
+
+An event handler which shows a spinning baton while it works. This is
+mainly used as the subsidiary event handler when generating Lim-Lee
+primes. There only needs to be one of these, so it's called
+B<$pg_evspin>.
+
+=item B<Catacomb::MP::Prime::Gen::Proc-E<gt>subev()>
+
+An event handler which works like B<ev()> above, but puts square
+brackets around its output. Also suitable for use in Lim-Lee
+generation. There only needs to be one of these, so it's called
+B<$pg_subev>.
+
+=back
+
+=head2 Prime generation
+
+Prime generation is driven by the procedure
+B<Catacomb::MP::Prime-E<gt>gen()>, which is also named B<primegen()> for
+convenience.
+
+=over
+
+=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<)>
+
+=item B<primegen(>I<name>B<,> I<m>B<,> I<nsteps>B<,> I<stepper>B<,> I<ntests>B<,> I<tester>B<,> [I<events>]B<)>
+
+Generates a prime number. It will start with the integer I<m>, and run
+the I<stepper> for at most I<nsteps> times (infinitely if I<nsteps> is
+zero), returning B<undef> if it fails. Each time the stepper reports a
+plausible candidate, it runs the tester up to I<ntests> times; it
+returns the candidate if all these tests succeeded. It will call the
+event handler after each step and test.
+
+=back
+
+=head2 Writing your own steppers, testers and event handlers
+
+As mentioned, steppers, testers and event handlers have similar
+interfaces. Each is represented by an object whose class is a
+descendent (via B<@ISA>) of B<Catacomb::MP::Prime::Gen::Proc>. The
+prime generator will call methods on your object as required.
+
+Event handlers are the easiest, so we deal with them first. All methods
+are called with one argument which is the event object. The methods
+called are as follows.
+
+=over
+
+=item B<PG_BEGIN>
+
+Prime generation has begun.
+
+=item B<PG_TRY>
+
+About to start testing a new number.
+
+=item B<PG_PASS>
+
+Number passed a primality test.
+
+=item B<PG_FAIL>
+
+Number failed a primality test.
+
+=item B<PG_DONE>
+
+Prime number found successfully.
+
+=item B<PG_ABORT>
+
+No prime number found; we gave up.
+
+=back
+
+Any of these methods may return B<PGEN_ABORT> (-1) to abandon prime
+searching. This is intended to be used, for example, by a progress
+dialogue box if its cancel button is pressed. Any other value is
+ignored.
+
+Here's a simple example of an event handler.
+
+ package Strange::Events;
+ @ISA = qw(Catacomb::MP::Prime::Gen::Proc);
+
+ sub new { bless {}, $_[0]; }
+
+ sub PG_BEGIN {
+ my ($me, $ev) = @_;
+ local $| = 1;
+ print $ev->name(), " [";
+ }
+
+ sub PG_PASS { local $| = 1; print "*"; }
+ sub PG_FAIL { local $| = 1; print "."; }
+ sub PG_ABORT { local $| = 1; print "] :-(\n"; }
+ sub PG_DONE { local $| = 1; print "]\n"; }
+
+Steppers use fewer methods, but are a bit more involved.
+
+=over
+
+=item B<PG_BEGIN>
+
+Initialize the stepper. Read the starting point from the event, or
+store a new starting point, as appropriate. Return B<PGEN_DONE> if the
+starting point is satisfactory, B<PGEN_ABORT> for failure, or B<PGEN_TRY>
+to run the tester.
+
+=item B<PG_TRY>
+
+Advance the stepper. Write the new number to the event. Return as for
+B<PG_BEGIN>.
+
+=item B<PG_DONE>
+
+All is over. Tidy up.
+
+=back
+
+Testers are similar.
+
+=over
+
+=item B<PG_BEGIN>
+
+Initialize the tester. Read the starting point from the event. Return
+B<PGEN_DONE> if the starting point is satisfactory, B<PGEN_PASS> if
+you've actually run a successful test, B<PGEN_FAIL> to reject the
+candidate, or B<PGEN_TRY> to proceed to testing.
+
+=item B<PG_TRY>
+
+Run a test. Return B<PGEN_DONE> if the number is satisfactory,
+B<PGEN_PASS> if it passed a test, or B<PGEN_FAIL> if it failed.
+
+=item B<PG_DONE>
+
+Testing is done. Tidy up.
+
+=back
+
+Finally, any method can return B<PGEN_ABORT> to stop prime generation in
+its tracks almost immediately. (The B<PG_DONE> methods are still called
+for the stepper, and for the tester if it's active.)
+
+It's probably best to do tidying in B<PG_DONE> rather than leaving it
+until B<DESTROY>, since testers and steppers and things may get left
+around for a while, espectially if they're simple.
+
+Since steppers and testers often work together, here's an example of a
+pair for generating I<Sophie Germain primes>. A prime number I<q> is
+Sophie-Germain prime if 2 I<q> + 1 is also prime. We work by
+maintaining separate filters and testing contexts for I<q> and 2 I<q> +
+1, and checking both in parallel. Generating Sophie Germain primes is a
+long job.
+
+ package SophieGermain::Stepper;
+ use Catacomb qw(:const :mp :pgen);
+ @ISA = qw(Catacomb::MP::Prime::Gen::Proc);
+
+ sub new { bless [undef, undef], $_[0]; }
+
+ sub _step {
+ my ($me, $ev) = @_;
+ while ($me->[0]->status() == PGEN_FAIL ||
+ $me->[1]->status() == PGEN_FAIL) {
+ $me->[0]->step(2);
+ $me->[1]->step(4);
+ }
+ $ev->m($me->[0]->m());
+ return PGEN_TRY;
+ }
+
+ sub PG_BEGIN {
+ my ($me, $ev) = @_;
+ my $x = $ev->m();
+ $me->[0] = $x->filter();
+ $me->[1] = (2*$x + 1)->filter();
+ _step($me, $ev);
+ }
+
+ sub PG_TRY {
+ my ($me, $ev) = @_;
+ $me->[0]->step(2);
+ $me->[1]->step(4);
+ _step($me, $ev);
+ }
+
+ sub PG_DONE {
+ my ($me, $ev) = @_;
+ $me->[0] = $me->[1] = undef;
+ }
+
+ package SophieGermain::Tester;
+ use Catacomb qw(:const :mp :pgen);
+ @ISA = qw(Catacomb::MP::Prime::Gen::Proc);
+
+ sub new { bless [undef, undef], $_[0]; }
+
+ sub PG_BEGIN {
+ my ($me, $ev) = @_;
+ my $x = $ev->m();
+ $me->[0] = $x->rabin();
+ $me->[1] = (2*$x + 1)->rabin();
+ return PGEN_TRY;
+ }
+
+ sub _test {
+ my ($r, $rabin) = @_;
+ my $w = $r->mprange($rabin->m());
+ return $rabin->test($w) == PGEN_PASS;
+ }
+
+ sub PG_TRY {
+ my ($me, $ev) = @_;
+ my $r = $ev->rand();
+ my $w = $r->mprange($me->[0]->m());
+ return _test($r, $me->[0]) && _test($r, $me->[1]) ?
+ PGEN_PASS : PGEN_FAIL;
+ }
+
+ sub PG_DONE {
+ my ($me, $ev) = @_;
+ $me->[0] = $me->[1] = undef;
+ }
+
~mdw / catacomb-perl / blobdiff