9
$\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$
  • $\begingroup$ Take a look at section 6 in ia.cr/2017/411 $\endgroup$ – j.p. May 18 '17 at 7:11
19
$\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: <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$.

$\endgroup$
  • $\begingroup$ 7 (2 -47x7) is equal to 2289 ? $\endgroup$ – user3834282 May 24 '17 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 '17 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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