12
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Take a look at section 6 in ia.cr/2017/411 $\endgroup$
    – j.p.
    May 18, 2017 at 7:11

1 Answer 1

23
$\begingroup$

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: <[email protected]>, 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$.

$\endgroup$
3
  • $\begingroup$ 7 (2 -47x7) is equal to 2289 ? $\endgroup$ May 24, 2017 at 9:02
  • $\begingroup$ @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$. $\endgroup$
    – fgrieu
    May 24, 2017 at 9:28
  • $\begingroup$ In "(that can be $x=a$, perhaps $\bmod 7$, which is the inverse for any odd $a$ over three bits)" did you mean to write $\bmod 8$, meaning truncating $a$ to the bottom three bits? In the example computation you seem to use $\bmod 8$, and I can't see how $\bmod 7$ would be correct. $\endgroup$ Sep 26, 2022 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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