From 076bdc812e0abbe466d927063cc8cb3d116154a2 Mon Sep 17 00:00:00 2001 From: cperciva Date: Fri, 26 Sep 2014 09:40:48 +0000 Subject: 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 | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'games/factor') 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. -- cgit v1.1 From a742fc39b4772b875eb540b6934da3350e9086e2 Mon Sep 17 00:00:00 2001 From: cperciva Date: Sat, 27 Sep 2014 09:00:38 +0000 Subject: Switch primes(6) from using unsigned long to using uint64_t. This fixes 'limited range of type' warnings about comparisons on 32-bit systems, and allows 32-bit systems to compute the full range of primes. --- games/factor/factor.6 | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'games/factor') diff --git a/games/factor/factor.6 b/games/factor/factor.6 index 508a98b..ba82f14 100644 --- a/games/factor/factor.6 +++ b/games/factor/factor.6 @@ -89,8 +89,7 @@ The value must not be greater than the maximum. The default and maximum value of .Ar stop -is 4294967295 on 32-bit architectures -and 3825123056546413050 on 64-bit ones. +is 3825123056546413050. .Pp When the .Nm primes -- cgit v1.1 From ac53ffbd58ec1112dd1fa9786a490a5c84f5ded6 Mon Sep 17 00:00:00 2001 From: sbruno Date: Sat, 27 Sep 2014 10:57:34 +0000 Subject: Update factor for changes to types in primes, which is a dependency. Fixes build-fail on mips32 introduced at 272207. --- games/factor/factor.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'games/factor') diff --git a/games/factor/factor.c b/games/factor/factor.c index 8b76c17..19fe830 100644 --- a/games/factor/factor.c +++ b/games/factor/factor.c @@ -69,6 +69,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include #include @@ -227,7 +228,7 @@ pr_fact(BIGNUM *val) /* Divide factor out until none are left. */ do { - printf(hflag ? " 0x%lx" : " %lu", *fact); + printf(hflag ? " 0x%" PRIx64 "" : " %" PRIu64 "", *fact); BN_div_word(val, (BN_ULONG)*fact); } while (BN_mod_word(val, (BN_ULONG)*fact) == 0); -- cgit v1.1