X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb-perl/blobdiff_plain/f9952aec1cf6c64a5681308eea817b6113a37433..fcd15e0b7a3d0f0ca2f30953573f8d1f6b8e8bd2:/Catacomb::MP::Prime.pod

diff --git a/Catacomb::MP::Prime.pod b/Catacomb::MP::Prime.pod
new file mode 100644
index 0000000..8bd543b
--- /dev/null
+++ b/Catacomb::MP::Prime.pod
@@ -0,0 +1,524 @@
+=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;
+    }
+