summaryrefslogtreecommitdiffstats
path: root/games/factor
diff options
context:
space:
mode:
authorcperciva <cperciva@FreeBSD.org>2014-09-26 09:40:48 +0000
committercperciva <cperciva@FreeBSD.org>2014-09-26 09:40:48 +0000
commit076bdc812e0abbe466d927063cc8cb3d116154a2 (patch)
tree2c904acd83780b58efdc8133cef392b90f95a976 /games/factor
parentb72b8c0a77fbe5de0dc565a6476866f20c2c633c (diff)
downloadFreeBSD-src-076bdc812e0abbe466d927063cc8cb3d116154a2.zip
FreeBSD-src-076bdc812e0abbe466d927063cc8cb3d116154a2.tar.gz
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
Diffstat (limited to 'games/factor')
-rw-r--r--games/factor/factor.68
1 files changed, 7 insertions, 1 deletions
diff --git a/games/factor/factor.6 b/games/factor/factor.6
index a4d35e9..508a98b 100644
--- a/games/factor/factor.6
+++ b/games/factor/factor.6
@@ -90,7 +90,7 @@ value must not be greater than the maximum.
The default and maximum value of
.Ar stop
is 4294967295 on 32-bit architectures
-and 18446744073709551615 on 64-bit ones.
+and 3825123056546413050 on 64-bit ones.
.Pp
When the
.Nm primes
@@ -120,3 +120,9 @@ cannot handle the
factor list,
.Nm primes
will not get you a world record.
+.Pp
+.Nm primes
+is unable to list primes between 3825123056546413050 and 18446744073709551615
+since it relies on strong pseudoprime tests after sieving, and nobody has
+proven how many strong pseudoprime tests are required to prove primality for
+integers larger than 3825123056546413050.
OpenPOWER on IntegriCloud