# How to determine the multiplicative inverse modulo 64 (or other power of two)?

I am trying to determine the multiplicative inverse of $47$ modulo $64$. So I have looked for an algorithm or scheme in order to perform this.

I found this wiki explaining how to find a multiplicative inverse. I tried to perform all the calculations, but the result was incorrect. I got $5$ as a multiplicative inverse, but this cannot be true: $47\times5\not\equiv1\pmod{64}$. Who can help me?

• Take a look at section 6 in ia.cr/2017/411 – j.p. May 18 '17 at 7:11

A boring method is to carefully apply the (partially) extended Euclidean algorithm.

But in the question, the modulus is a power of two (specifically $$2^6$$), and we can use that $$a\,x\equiv1\pmod{2^k}\implies a\,x\,(2-a\,x)\equiv1\pmod{2^{2k}}$$ from which it follows this fact:

if the modular inverse of $$a$$ modulo $$2^k$$ is (the lower $$k$$ bits of) $$x$$, then
the modular inverse of $$a$$ modulo $$2^{2k}$$ is (the lower $$2k$$ bits of) $$x\,(2-a\,x)$$
(where negative integers are in 2's-complement convention, dominant in modern CPUs).

This not-so-much-known fact allows computation of multiplicative inverse modulo $$2^k$$. We start from an inverse $$x$$ of $$a$$ over few bits (that can be $$x=a$$, perhaps $$\bmod 7$$, which is the inverse for any odd $$a$$ over three bits), and iterate $$x\gets x\,(2-a\,x)$$, possibly truncated to the number of known-correct result bits. That number of bits doubles at each iteration, thus about $$\log_2(k)$$ steps are enough, and it is only used product, subtraction, and bit truncation on values no wider than $$k$$ bits. That is blindingly fast compared to the Euclidean algorithm's $$O(k)$$ steps; and eases getting data-independent execution time, which comes handy in some cryptographic computations (e.g. the preliminary computation of $$m'$$ in Montgomery multiplication, algorithm 14.36 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography).

I learned the technique from Colin Plumb's Computing multiplicative inverses (post on sci.crypt with Message-ID: <1994Apr6.093116.27805@mnemosyne.cs.du.edu>, 1994). His statement applies to inverse modulo a prime power, and points the relation to the Newton's iteration for finding $$x = 1/a$$ in $$\Bbb R$$.

A modern exposition, with benchmarks, is in Jean-Guillaume Dumas: On Newton-Raphson iteration for multiplicative inverses modulo prime powers.

A bibliography, and other techniques faster than the Euclidean algorithm, are in Çetin Kaya Koç: A New Algorithm for Inversion mod $$p^k$$.

Here, to perform the desired computation quickly, we use $$k=3$$, $$a=47$$, and compute $$a\bmod2^k=47\bmod8=7$$, which multiplicative inverse modulo $$8$$ is also $$x=7$$. Now we compute \begin{align} (x\,(2-a\,x))\bmod2^{2k}&=(7\,(2-47\times7))\bmod 64\\ &=15\end{align}

Hence the desired modular inverse of $$47$$ modulo $$64$$ is $$15$$.

• 7 (2 -47x7) is equal to 2289 ? – user3834282 May 24 '17 at 9:02
• @user3834282: Actually, $7(2-47\times 7)$ is $-2289$, and $(-2289)\bmod64$ is $15$. Recall the definition of $\bmod$ as an operator: $u\bmod v$ is the (uniquely defined) $w$ such that $0\le w<v$ and $v$ divides $u-w$. For $u\ge0$, $w$ is the remainder of the Euclidean division of $u$ by $v$. For negative $u$, one can use the trivially established: $(u\bmod v)=(v-1)-((1-u)\bmod v)$. Apply with $u=-2289$ and $v=64$. Do not confuse with $w\equiv u\pmod v$ [notice the $\equiv$ and the $($ immediately before $\bmod$], which only tells that $v$ divides $u-w$, and does not uniquely define $w$. – fgrieu May 24 '17 at 9:28