readme.germtest

包含哈希,对称以及非对称的经典算法 包含经典事例

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...