# What's the internal state size and output range of mrg32k3a?

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?

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.

• So the state is - for all practical purposes - $8 \cdot 32 = 256$ bits, right? – Maarten Bodewes Nov 19 '18 at 13:51
• I added the modules, too. Usually, they are not considered as states. But if you think about all the memory requirements, yes. – kelalaka Nov 19 '18 at 13:56
• 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. – user45491 Nov 19 '18 at 17:53