# How to find the public key in RSA?

Finding the public key given the private key $d$ and the prime numbers $p$ and $q$.

$$p = 3092551601$$

$$q = 3490383433$$

$$d = 10719928016004921607$$

Since this is RSA, here is my thinking.

In order to find the public key $e$ it must satisfy this equation

$$d\cdot e=1 \mod \varphi(n)$$ Since I am looking for $e$, $$(e \cdot 10719928016004921607) \mod 10794190867245091200=1$$ However, after this step is where I am lost.

I tried using basic mathematics but it gives me the inverse of $d$. Plus, I don't think that using brute force is the right way to learn or understand this question.

• Technically $e$ is the public exponent, and $e$ together with $n$ make up the full public key. – Nayuki Apr 1 '18 at 23:39

You indeed need the inverse of $d$, but it's the so-called modular (multiplicative) inverse.

This can be done with the Extended Euclidean algorithm. You basically compute the greatest common divisor of $d$ and $\varphi(n)$ (you know already that it's going to be 1) and use the intermediate results to get the value of $e$.

The following simple Java program implements this algorithm, prints the result ($e = 8601051999309708343$) and proves it's indeed the multiplicative inverse (modulo $\varphi(n)$ of $d$.

List<BigInteger> q = new ArrayList<>(), r = new ArrayList<>(), s = new ArrayList<>(), t = new ArrayList<>();
int i = 0;
do {
i++;
BigInteger[] results = r.get(i - 1).divideAndRemainder(r.get(i));
if (results[1].compareTo(BigInteger.ZERO) == 0) {
break;
}
} while (true);

BigInteger lastS = s.get(s.size() - 1);
System.out.println(lastS.mod(r.get(1)) + ", " + lastS.multiply(r.get(0)).mod(r.get(1)));


It takes 15 steps to get to this result, it's rather hard to do that by hand.