]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/commit
Correctly enumerate primes between 4295098369 and 3825123056546413050.
authorcperciva <cperciva@FreeBSD.org>
Fri, 26 Sep 2014 09:40:48 +0000 (09:40 +0000)
committercperciva <cperciva@FreeBSD.org>
Fri, 26 Sep 2014 09:40:48 +0000 (09:40 +0000)
commit076bdc812e0abbe466d927063cc8cb3d116154a2
tree2c904acd83780b58efdc8133cef392b90f95a976
parentb72b8c0a77fbe5de0dc565a6476866f20c2c633c
Correctly enumerate primes between 4295098369 and 3825123056546413050.

Prior to this commit, primes(6) relied solely on sieving with primes up
to 65537, with the effect that composite numbers which are the product
of two non-16-bit primes would be incorrectly identified as prime.  For
example,
# primes 1099511627800 1099511627820
would output
1099511627803
1099511627807
1099511627813
when in fact only the first of those values is prime.

This commit adds strong pseudoprime tests to validate the candidates
which pass the initial sieving stage, using bases of 2, 3, 5, 7, 11,
13, 17, 19, and 23.  Thanks to papers from C. Pomerance, J.L. Selfridge,
and S.S. Wagstaff, Jr.; G. Jaeschke; and Y. Jiang and Y. Deng, we know
that the smallest value which passes these tests is 3825123056546413051.

At present we do not know how many strong pseudoprime tests are required
to prove primality for values larger than 3825123056546413050, so we
force primes(6) to stop at that point.

Reviewed by: jmg
Relnotes: primes(6) now correctly enumerates primes up to
3825123056546413050
MFC after: 7 days
Sponsored by: EuroBSDCon devsummit
games/factor/factor.6
games/primes/Makefile
games/primes/primes.c
games/primes/primes.h
games/primes/spsp.c [new file with mode: 0644]