0
$\begingroup$

I have been looking into PRNGs and stumbled upon the efficient Jump Ahead implementation for Multiplicative Lagged Fibonacci Generator. The technique relies on the fact that any odd integer $X$ can be uniquely represented modulo $2^m$ as $x \equiv (-1)^y 3^z \mod 2^m$, where $y \in \{0,\ 1\}$ and $z \in \{0,\ \ldots,\ 2^{m-2}-1\}$. I find myself unable to prove this fact or find anything on the Internet.

I would greatly appreciate it if someone could help me proving this.

$\endgroup$
3
  • $\begingroup$ For $m=1$ the statement is prettty much that any odd integer is odd. For $m=2$ the statement is also quite uninteresting. $\endgroup$ Apr 3, 2018 at 9:41
  • 1
    $\begingroup$ Try to prove that the order of 3 modulo $2^m$ is $2^{m-2}$. The Binomial Theorem might help ($3^r=(2+1)^r=\cdots$). $\endgroup$ Apr 3, 2018 at 10:05
  • $\begingroup$ @GerryMyerson I'm sorry, but I don't see how Binomial Theorem helps here. Though I see that the order is at most $2^{m-1}$ due to Euler's Theorem. $\endgroup$ Apr 3, 2018 at 13:04

1 Answer 1

1
$\begingroup$

For any $n\geq 3$ we have $$\mathbb{Z}/(2^n \mathbb{Z})^* \simeq \mathbb{Z}/(2^{n-2} \mathbb{Z})\rtimes\mathbb{Z}/(2\mathbb{Z})$$ and every element of $\mathbb{Z}/(2^n \mathbb{Z})^*$ can be represented as $\pm 5^h$ since $5\equiv 1\pmod{4}$, $5$ generates the quadratic residues in $\mathbb{Z}/(8\mathbb{Z})^*$ and we may apply the Hensel lifting lemma. We have something similar (namely, your statement) if $5$ is replaced by $3$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .