diff options
| author | cperciva <cperciva@FreeBSD.org> | 2014-09-26 09:40:48 +0000 |
|---|---|---|
| committer | cperciva <cperciva@FreeBSD.org> | 2014-09-26 09:40:48 +0000 |
| commit | 076bdc812e0abbe466d927063cc8cb3d116154a2 (patch) | |
| tree | 2c904acd83780b58efdc8133cef392b90f95a976 /games/primes/primes.h | |
| parent | b72b8c0a77fbe5de0dc565a6476866f20c2c633c (diff) | |
| download | FreeBSD-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/primes/primes.h')
| -rw-r--r-- | games/primes/primes.h | 9 |
1 files changed, 9 insertions, 0 deletions
diff --git a/games/primes/primes.h b/games/primes/primes.h index 0951bbf..7dcef52 100644 --- a/games/primes/primes.h +++ b/games/primes/primes.h @@ -57,6 +57,9 @@ typedef unsigned long ubig; /* must be >=32 bit unsigned value */ extern const ubig prime[]; extern const ubig *const pr_limit; /* largest prime in the prime array */ +/* Maximum size sieving alone can handle. */ +#define SIEVEMAX 4295098368ULL + /* * To avoid excessive sieves for small factors, we use the table below to * setup our sieve blocks. Each element represents an odd number starting @@ -64,3 +67,9 @@ extern const ubig *const pr_limit; /* largest prime in the prime array */ */ extern const char pattern[]; extern const size_t pattern_size; /* length of pattern array */ + +/* Test for primality using strong pseudoprime tests. */ +int isprime(ubig); + +/* Maximum value which the SPSP code can handle. */ +#define SPSPMAX 3825123056546413050ULL |
