2
$\begingroup$

For educational purpose, I need a very short random number generator. Then I tried to use a linear consequential generator with modulo equal to 5, expecting a length (period) equal to 5.

Following the rules described in https://en.wikipedia.org/wiki/Linear_congruential_generator#c%E2%89%A00 , I choose :

$a=4$, $c=1$, $m=5$ and $X_0=0$.

These values generate the sequence 1 0 1 0 1...

$X_0=2$ generates 4 2 4 2... and $X_0$=3 generates 3 3 3...

I do not understand which rule I infringe as :

  • 1st rule : $m$ being a prime number, any $c$ would be prime with it ;

  • 2nd rule : $m$ being a prime number, it has no prime factors, then any $a$ would be right

  • 3nd rule does not apply as $m$ is not a multiple of 4

Obviously, I am wrong.

I would appreciate any comment.

$\endgroup$

1 Answer 1

0
$\begingroup$

The period is a factor of $\phi(m)$. To get the maximum period, $\phi(m)$, $a$ must be a primitive root modulo $m$. If $m$ is prime, $\phi(m)=m-1$.

For example, the primitive roots modulo 17 are 3, 5, 6, 7, 10, 11, 12, 14.

Modulo 5, $4=-1$ is not a primitive root, but has order 2. Hence your observation that the sequence of numbers coming from your generator has period 2.

Picking $a$ from a particular residue class mod 4 is no guarantee of success (nor of failure). Perhaps OP was thinking of the advice for picking parameters for a LCG when $m$ is a power of 2? Then indeed, $a=1\mod 4$ is best, and will give a period of $\phi(m)=m/2$.

$\endgroup$

You must log in to answer this question.