mdw@git.distorted.org.uk Git - catacomb-perl/blob - Catacomb::MP::Prime.pod

   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();
 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