On 2014-02-28 22:22, Geoffrey Keating wrote:
I'd encourage you to do the derivation again: compute
2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
and verify that it's prime. I don't think any special security
measures were taken during the creation of RFC 3526, you'd think by
now someone would have noticed if the 'primes' weren't prime or didn't
match the claimed polynomial, but if everyone thinks someone else has
checked...
There is more.1. The MODP primes are supposed to be safe primes (i.e. primes on the form p = 2q+1 where q is also prime). Furthermore, 2 will be a generator of the large sub group of order q, rather than of the entire multiplicative group of order 2q.
2. Pi might be calculated using the Bailey–Borwein–Plouffe formula. I calculated it for the first 2048 hexadecimal digits, which was a sufficiently good approximation for all of the MODP groups up to the 8192 bit one.
3. All of the MODP primes are on the form p = 2^n - 2^(n-64) + 2^64( [2^(n-130)pi] + k). The value k is supposed to be the least positive integer, such that p is a safe prime. This check is important, to rule out that any candidates have been deliberately skipped, because they lack some (hidden) property.
I have generated the primes 1024, 2048, 3072, 4096, 6144 and 8192 from the formulae and verified that:
a: The numbers match the numbers in the RFCs.b: The numbers are safe primes (using both Miller-Rabin tests and Lucas tests on q = (p-1)/2, and then the Pocklington Criterion on p). c: The small constant k is indeed the least positive integer such that the number is a safe prime. (Well, to be honest I am still running this test for the largest group, just make sure once more.)