2
$\begingroup$

This is Pierre L'Ecuyer's PRNG. I know its period is $2^{191}$, but I don't know what is its internal state size. What is it?

$\endgroup$
2
$\begingroup$

The answer is based on the given period construction from your link.

You have to store the two modulus

  • $m_1 = 2^{32} − 209 = 4294967087$ and
  • $m_2 = 2^{32} − 22853 = 4294944443,$

and the internal states are;

  • $s_{1,n} = \{x_{1,n},x_{1,n+1}, x_{1,n+1} \}$ and
  • $s_{2,n} = \{x_{2,n},x_{2,n+1}, x_{2,n+1} \}$.

The $z_n = (x_{1,n}- x_{2,n}) \bmod m_1$, evolves with this $x_{1,n}$ and $x_{2,n}$ where each requrrence relation for $x_{1,n}$ and $x_{2,n}$ is taken module $m_1$ and $m_2$, respectively;

$$x_{1,n} = (1403580 \times x_{1,n-2} - 810728 \times x_{1,n-3} ) \bmod m_1,$$ $$x_{2,n} = (527612 \times x_{2,n-2} -1370589 \times x_{2,n-3} ) \bmod m_2$$

Therefore you need to store 3 moduli $m_1$ and 3 moduli $m_2$ internal states.

The $m_1$ and $m_2$ is very close to $2^{32}$, so we can say that you need;

  • 6 unsigned 32-bit integers for the internal states.
  • For the modulus, you will also need 2 unsigned 32-bit integers.

the range is $m_1$ since the $z_n$ is taken $\mod m_1$.

Yes; the state for all practical purposes is $8 \cdot 32=256$-bit.

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ So the state is - for all practical purposes - $8 \cdot 32 = 256$ bits, right? $\endgroup$ – Maarten Bodewes Nov 19 '18 at 13:51
  • 1
    $\begingroup$ I added the modules, too. Usually, they are not considered as states. But if you think about all the memory requirements, yes. $\endgroup$ – kelalaka Nov 19 '18 at 13:56
  • $\begingroup$ Thank you so much for clearly showing the steps. Interesting question about considering or not considering the modules. I would not consider them since they will not make anything harder on the adversary's side. $\endgroup$ – user45491 Nov 19 '18 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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