# How expensive is the Extended Euclidean Algorithm?

Given a private key $k$ and a modulus $n=pq$, where $p \neq q$ are two very large prime numbers, we find the value of Euler's Totient Function $\varphi(n)=(p-1)(q-1)$. The public key $K$ is given by the multiplicative inverse of the private key, modulo $\varphi(n)$, i.e. $kK \equiv 1 \bmod \varphi(n)$.This is often written as $K = k^{-1} \pmod{\varphi(n)}$.

The extended Euclidean algorithm can by used to find $K$. Assuming that $k$ and $\varphi(n)$ are coprime, i.e. $\gcd(k,\varphi(n))=1$, we can find integers $s$ and $t$ for which $ks + \varphi(n)t=1$. The multiplicative inverse of $k$, i.e. the public key $K$, will be given by $s$.

Assuming that $n=pq$ is a very large number, say 1024 bit or larger, it follows that $\varphi(n)=(p-1)(q-1)$ will also be a very large number.

How "expensive" is it, or how long would it take, to compute the multiplicative inverse of $k \pmod{\varphi(n)}$ using the extended Euclidean algorithm? How does this "expense"/time compare to factorise $n$?

• If you know $k$ and $\varphi(n)$, computing the multiplicative inverse of $k$ $\pmod{\varphi(n)}$ is only a few times more costly than division of $\varphi(n)$ by $k$; that is, in practice, inexpensive. It you only know $k$ and $n$, computing the multiplicative inverse of $k$ $\pmod{\varphi(n)}$ is about as hard as factoring $n$. – fgrieu Jan 5 '17 at 20:59
• The fact that the EEA is cheap (or equivalently, that computing GCDs and modular inverses is easy) is absolutely fundamental, and you should look into it seriously with a good computational number theory textbook. – fkraiem Jan 5 '17 at 21:16
• By the way, if you only know the modulus $n$, then the EEA is irrelevant since you do not know $\varphi(n)$ (so you cannot run the EEA on it). – fkraiem Jan 5 '17 at 21:54
• @fkraiem But I'm the private key holder, so I know $p$ and $q$ where $n=pq$. – Fly by Night Jan 6 '17 at 15:37
• Right, then the previous comment applies. – fkraiem Jan 6 '17 at 19:44

If you have two positive integers $a>b>0$ with $n_1,n_2$ bits respectively, you need $O(n_1n_2)$ running time to compute integers $d,s,t$ such that $d=\gcd(a,b)$ and $d=as+bt$ (this is theorem 4.4 of Victor Shoup book). In your case (since you know $\phi(N))$ set $a=K, b=\phi(N)$ to compute $k$ (as you desrcibed) in time $O( len(\phi((N))\cdot len(k) ).$
• Thank you very much for your answer. What is $\operatorname{len}(k)$? – Fly by Night Jan 6 '17 at 17:59
• Thanks for that. What would the running time for the factorisation of $n$ be in terms of $\operatorname{len}(p)$ and $\operatorname{len}(q)$, where $n=pq$, be? – Fly by Night Jan 6 '17 at 18:21
• Let's say I'm a public key holder (so I know the modulus $n$ and public key $K$). How hard is it to factorise $n$? The motivation for my question is (quite naively): using RSA is "easy" and uses the EEA which depends on division of very large numbers, but the "hard" problem of factorising is also a division problem. What is the relative difficulty of using the EEA to find the public key $K = k^{-1} \pmod{\varphi(n)}$ compared to factoring $n$ given $K$? – Fly by Night Jan 6 '17 at 21:15