Question

The power generator is a method for generating pseudorandom numbers. To use the power generator, parameters p and dare specified, where p is a prime, d is a positive integer such that p| d, and a seed x0 is specified. The pseudorandom numbers $\mathbf{x}\mathbf{1}\mathbf{,}\mathbf{x}\mathbf{2}\mathbf{,}\mathbf{\dots }$are generated using the recursive definition $\mathit{x}\mathit{n}\mathbf{+}\mathbf{1}\mathbf{=}\mathit{x}\mathit{d}\mathit{n}\mathbf{mod}\mathit{p}$.

11. Find the sequence of pseudorandom numbers generated by the power generator with $\mathit{p}\mathbf{=}\mathbf{7}\mathbf{,}\mathit{d}\mathbf{=}\mathbf{3}$, and seed $\mathit{x}\mathbf{0}\mathbf{=}\mathbf{2}$.

Short answer

$\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}$

Step-by-step solution

Step 1

${\mathit{x}}_{\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{=}{\mathit{x}}_{\mathbf{d}}^{\mathbf{n}}$

We are asked to find the sequence of pseudorandom numbers, so we use the formula that we are given.

And

$\mathit{p}\mathbf{=}\mathbf{7}\mathbf{,}\mathit{d}\mathbf{=}\mathbf{3}\mathbf{,}{\mathit{x}}_{\mathbf{0}}\mathbf{=}\mathbf{2}$

Step 2

$$\begin{gathered} {\mathit{x}}_{\mathbf{1}}\mathbf{=}{\mathbf{2}}^{\mathbf{3}}\mathbf{(}\mathbf{mod}\mathbf{7}{\mathbf{)}}^{\mathbf{\circ }}\mathbf{8}\mathbf{(}\mathbf{mod}\mathbf{7}{\mathbf{)}}^{\mathbf{\circ }}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{7}\mathbf{)} \\ \mathbf{\times }\mathbf{2}\mathbf{=}{\mathbf{1}}^{\mathbf{3}}\mathbf{(}\mathbf{mod}\mathbf{7}{\mathbf{)}}^{\mathbf{\circ }}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{7}\mathbf{)} \\ \mathbf{\times }\mathbf{3}\mathbf{=}{\mathbf{1}}^{\mathbf{3}}\mathbf{(}\mathbf{mod}\mathbf{7}{\mathbf{)}}^{\mathbf{\circ }}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{7}\mathbf{)} \end{gathered}$$

We substitute ${\mathit{x}}_{\mathbf{0}}$into the equation and find that${\mathit{x}}_{\mathbf{1}}\mathbf{=}\mathbf{1}$, but if we continue powering$\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{7}\mathbf{)}$, we will soon find out that this sequence never ends. So, the sequence generated is:

$\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{1}$