Update for new keydata interface.

[catacomb-perl] / Catacomb::MP::Prime.pod

=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();
      return _test($r, $me->[0]) && _test($r, $me->[1]) ? 
        PGEN_PASS : PGEN_FAIL;
    }

    sub PG_DONE {
      my ($me, $ev) = @_;
      $me->[0] = $me->[1] = undef;
    }