Modification of Linear Congruential Generator

[ttw]

The LCD RNG is commonly used, mostly because it's deficiencies are well-understood. The modulus does need to be large to be useful. For example, in practice, the RNG X=X*5^19 mod 2^48 was popular (and probably still is) in much scientific work. Fischman has a paper comparing this generator (which is not a very good 48 or 46-bit generator) with all possible 32-bit generators. This 48-bit (actually cycle length 2^46) generator is better than the best 32-bit generator (correlation, distribution, cycle length).

One problem with a power-of-2 modulus is that the last bits have a simple structure. The bottom bit has a cycle of 2, the next bit has a cycle of 4, etc. There has been some discussion (on the internet) of using 128-bit generators (I've been using a 256-bit but not a very good one) and discarding the lowest few bits. Actually, the upper bits have a structure but it's not particularly harmful. The leading bit has a cycle of 2^m for an m-bit generator so the leading bit of a 32-bit generator has a cycle of 2^32. This cycle consists of a string of length 2^31 followed by the complementary string, also of length2^31. The second from the leading bit has a similar structure.

To make bits appear less structured, a large prime modulus can be used. (This generator is never mixed and only misses the number 0.) The disadvantage is that more arithmetic is needed and the parameters are not as easy to find. In the binary case, any multiplier congruent to 3 or 5 modulo 8 gives a full cycle (thus the popularity of powers of 5). For a prime modulus, the multiplier has to be a primitive root which takes a bit of work to find.

With binary moduli, the low order bits between different multipliers (and different moduli) are related. A cycle of 2^k (bit k from the bottom of any binary generator) from 2 different generators will have the same difference thus possibly introducing correlation into a computation. The length of the sequence produced by using 2 binary generators is the same as that of the longer generator. With primes, the length of combined cycles is the LCM of the two generators (the LCM of P-1 and Q-1 for prime generator using P and Q). The prime modulus generators are "independent" in that two of them will fill a square with more random-looking patterns than binary generators do. Thus prime-moduli generators often use Sophie-Germain primes (or "safe" primes) (primes of the form 2*P+1 with P prime.)

In all cases, the continued from A/M where A is the multiplier and M is the modulus, should have all "small" partial quotients. (A large partial quotient means that the entire cycle seems to be made of a few long cycles.)

Now, the "new" (at least I've not seen this idea and I've searched.) It's well-known (among number theorists anyway) that the quadratic residues of a prime are "randomly" distributed (the exact distribution isn't known.) A quadratic residue is a number A for which x^2=A mod P has a solution.The pattern of residues of different primes are "independent" in general. Also, with primes of form 4*P+1, there are P quadratic residues less than 2*P and P above (half of the numbers modulo a prime are residues and half are not.) For primes of for 2*P+1 this is not true (sometimes by a lot). (There's no name for 4*P+1 primes like that for 2*P+1; I'll call them 41-primes and the other 43-primes.)

A quadratic residue cannot be a primitive root. The product of two residues or two non-residues is a residue and the product of a residue and a non-residue is a non-residue.

So here's my method (tested since I thought of it this morning): let the modulus be a prime of form 4*P+1 where P is a prime (I have a nice H50g program to do this). Go through the primitive roots (I think there are P of them so they are common) and for a primitive root B, compute A = B^2 mod 4*P+1. This A will be the multiplier for modulus M-4*P+1. Screen the possible values of A so that A/M developed as a continued fraction has "small" (1,2,3,4...) partial quotients. Then X=X*A mod M is the generator. It has a period of either 2*P and will cycle through the quadratic residues or the non-residues depending on the initial seed. The idea is to use the "randomness" of the quadratic residues to further mix the cycles. Basically, one is "randomly" cycling something more "random" that the sequence 1,2,3,4,....


Short example: M=61493, A=27614 Cycle length: 32746 (fits in 32 bits)

Long example: M=274877910173, A=52905939427 Cycle length: 137438955086 (still small enough that the HP50g doesn't screw up computations)

None of these are cryptographically secure. Lattice reduction (among others) gives parameters that produce the same cycle. More anon; the stuff I have been working on gave the above as a side trip.