| 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 | |