Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us assume a sequence as follows:

$S_{n} = (S_{n-1} * c_{1} + c_{2})\text{ mod } m$

This is the pseudorandom generator found in most programming languages' random function.

It is known that a prime $m$ results in a more uniform distribution of random numbers, as a result of a larger period for $S_{n}$. As a result, $m$ is typically a prime number.

Why do prime numbers typically result in larger periods than factorable numbers for modulo arithmetic?

share|improve this question
    
Have you seen the closed form formula for $S_n$? –  Gerry Myerson Apr 16 '13 at 6:03
    
@GerryMyerson I haven't; I'll look that up. –  Emrakul Apr 16 '13 at 6:04
add comment

1 Answer 1

up vote 3 down vote accepted

According to Wikipedia, the period is at most $m$, and is equal to $m$ only if

  1. $\gcd(c_2,m)=1$,

  2. $p\mid m$ implies $p\mid c_1-1$ for all prime $p$, and

  3. $4\mid m$ implies $4\mid c_1-1$.

So $m$ needn't be prime, but it's easiest to meet and to check these conditions if it is.

share|improve this answer
    
That's interesting. I'm curious how the proof of those three lemmas work, but I suppose I shall have to read the paper! Thank you! –  Emrakul Apr 17 '13 at 4:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.