Mathematics desk
< January 10	<< Dec \| January \| Feb >>	January 12 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 11

Generating random numbers with prime numbers

Thinking of ways to produce uniformly-distributed random numbers, I started with the simple function f(x) = x * p mod q, where x is some natural number and p, q are large primes of roughly the same magnitude. That alone does not however seem to be very "sufficient". I would like the sequences {f(1), f(2), f(3), ...} and {f(x), f(f(x)), f(f(f(x))), ...} to be not highly-correlated. Then it occurred to me that the following construction might work. Define g(x) = x * r mod s, where r and s are also primes. Then we simple define our "random transformation" as h(x) = f(g(x)). Does that really mitigate most of the correlation though (or perhaps am I severely mistaken)? Also, could it be done with fewer than 4 primes? Earl of Arundel (talk) 20:36, 11 January 2023 (UTC)[reply]

~~This is a special case of a linear congruential generator.~~ Knuth vol 2 has an extensive section on them, which is worth reading. They're flawed in several ways, and largely of historical interest at this point, but they are extremely simple to implement using very little memory and good enough for many simple tasks. --Trovatore (talk) 20:56, 11 January 2023 (UTC)[reply]

Oops; now I see I didn't read your post very carefully. I didn't take your separate f and g into account. Just the same you could do worse than read the material in Knuth for background. --Trovatore (talk) 22:58, 11 January 2023 (UTC)[reply]

No worries, I appreciate the suggestion anyhow. I haven't read anything by Knuth in years! Earl of Arundel (talk) 02:50, 12 January 2023 (UTC)[reply]

If

q

is a prime, it does not really matter whether

p

is also a prime. Taking

q=11,

and writing "A" for the number 10, the sequences produced for varying values of

p

for

f(1),f(2),f(3),...

and

f(1),f(f(1)),f(f(f(1))),...

are:

    p = 2:  2 4 6 8 A 1 3 5 7 9  2 4 8 5 A 9 7 3 6
    p = 3:  3 6 9 1 4 7 A 2 5 8  3 9 5 4 1 3 9 5 4
    p = 4:  4 8 1 5 9 2 6 A 3 7  4 5 9 3 1 4 5 9 3
    p = 5:  5 A 4 9 3 8 2 7 1 6  5 3 4 9 1 5 3 4 9
    p = 6:  6 1 7 2 8 3 9 4 A 5  6 3 7 9 A 5 8 4 2
    p = 7:  7 3 A 6 2 9 5 1 8 4  7 5 2 3 A 4 6 9 8
    p = 8:  8 5 2 A 7 4 1 9 6 3  8 9 6 4 A 3 2 5 7
    p = 9:  9 7 5 3 1 A 8 6 4 2  9 4 3 5 1 9 4 3 5

This shows that some choices for

p

are better than others when iterating

f

, but this is not related to the primality of

p

: 6 and 8 do better than 3 and 5. --Lambiam 00:26, 12 January 2023 (UTC)[reply]

Or is it because numbers less than q/2 are just bound to produce the worst sequences? Either way, that is very interesting indeed. So the fact that it doesn't matter whether or not p is prime, is that because multiplication over a finite field is a bijection? I still can't quite wrap my head around it. Having tested this using some REALLY big prime moduli, it seems that the h(x) = f(g(x)) approach looks pretty promising. Even when I set p to the same number for both functions, the result appears incredibly random. (And thanks to you, using less primes too!) Earl of Arundel (talk) 02:50, 12 January 2023 (UTC)[reply]

If the orbit of

f

does not repeat prematurely – as it does above for

3,4,5

and

9

– but cycles through a full permutation of

\{1,2,...,q{-}1\},

the number

p

is called a primitive root of the modulus

q.

As you can see in the table in the article, these are equally often less than as greater than half the modulus. --Lambiam 13:43, 12 January 2023 (UTC)[reply]

Oh yes! And in this case, q is always a safe-prime, so (correct me if I am wrong here) if q is also congruent to 3 mod 8, then 2 will definitely be a primitive root of q? Earl of Arundel (talk) 15:55, 13 January 2023 (UTC)[reply]

Indeed, if

q

is both a safe prime and

q\not \equiv \pm 1~~({\text{mod}}~8),

the number

2

is a generator of the multiplicative group modulo

q

. --Lambiam 17:47, 13 January 2023 (UTC)[reply]

Brilliant, thank you once again, Lambiam. This is really turning out to be a very interesting project! Earl of Arundel (talk) 19:01, 13 January 2023 (UTC)[reply]

The Xorshift pseudo-random number generators devised by George Marsaglia are a nice alternative if you want something really quick and simple rather than cryptographically secure. The variants that employ a simple scrambling of the output are better. catslash (talk) 01:39, 12 January 2023 (UTC)[reply]

You know, I actually have used those pretty extensively in the passed. The give decent results, and blazing fast. But still somewhat lacking in terms of producing a truly uniformly distributed output. Earl of Arundel (talk) 02:50, 12 January 2023 (UTC)[reply]