README.germtest
上传用户:zbbssh
上传日期:2007-01-08
资源大小:196k
文件大小:2k
- Test driver for Sophie Germain prime generation.
- Generating Sophie Germain primes is the most computationally expensive
- thing the math library does at present. Sophie Germain primes,
- (also known as "strong primes," although that term is used to mean
- a variety of thints) are odd primes p such that q = (p-1)/2 is also
- prime. It can take a *long* time to fine large (2000-bit and
- up) primes.
- The command line is a seed string which is used, along with a
- compiled-in list of prime sizes, to generate the initial search point
- for the prime. The first (probable) prime after that point is
- printed.
- germtest Hello, world
- germtest `cat /etc/motd`
- With the "Hello, world" seed, you will see the uncertainty in the
- generation time, as a 1024-bit prime is generated much faster than a
- 768-bit prime.
- The random-number generator used internally is George Marsaglia's
- multiply-with-carry "mother of all random number generators", which
- has an interesting relationship to Sophie Germain primes.
- The generator is based on the recurrence:
- (carry, x[i]) = carry + a1 * x[i-1] + a2 * x[i-2] + ... + ak * x[i-k].
- Where x[i] is the result modulo some base b (in germtest.c, b = 65536),
- and carry is the overflow, the sum divided by 65536.
- The properties of the generator are controlled by the parameter m,
- where m = ak * b^k + ... + a2 * b^2 + a1 * b - 1. (The "-1" term
- is the coefficient of x[i].) For example, the generator used has
- (a1, ..., a8) = (1941, 1860, 1812, 1776, 1492, 1215, 1066, 12013)
- This corresponds to
- m = 0x2EED042A04BF05D406F0071407440794FFFF
- The output of the generator is, in reverse order, the base-b digits
- of r/m, for some 0 < r < m. (Which r depends on the seed.)
- If m is a Sophie Germain prime, and b a power of 2, then the period
- of the generator will be the prime (m-1)/2. I.e. the period
- of the generator is 1577399102372415483554202684831355506491391,
- 1.577 * 10^42, or over 2^140.
- With a bit of hacking, this library could be used to search for such
- primes quickly, using a combination of the primeGenStrong code
- (which searches an arithmetic sequence for primes) and germainPrimeGen,
- which finds Sophie Germain primes. Maybe in the next release...