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.
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&lt;BigInteger&gt; q = new ArrayList&lt;&gt;(), r = new ArrayList&lt;&gt;(), s = new ArrayList&lt;&gt;(), t = new ArrayList&lt;&gt;();
q.add(BigInteger.ZERO);
r.add(new BigInteger("10719928016004921607"));
r.add(new BigInteger("10794190867245091200"));
s.add(BigInteger.ONE);
s.add(BigInteger.ZERO);
t.add(BigInteger.ZERO);
t.add(BigInteger.ONE);
int i = 0;
do {
    i++;
    BigInteger[] results = r.get(i - 1).divideAndRemainder(r.get(i));
    q.add(results[0]);
    r.add(results[1]);
    if (results[1].compareTo(BigInteger.ZERO) == 0) {
        break;
    }
    s.add(s.get(i - 1).subtract(q.get(i).multiply(s.get(i))));
    t.add(t.get(i - 1).subtract(q.get(i).multiply(t.get(i))));
} 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.