It's asked how, in RSA, one finds $e$ given $d$ and $N$. I'll ignore the question's requirement that $e$ is coprime with $N$, which is highly unusual and has no mathematical relevance. I'll also assume $p\ne q$, because it's necessary for the stated $\varphi(N)=(p-1)\cdot(q-1)$ to hold.
With the question's definition of RSA, the method to find $e$ goes
- Factor $N$ to find $p$ and $q$
- Compute $\varphi=(p-1)\cdot(q-1)$
- Compute $e$ knowing $e\cdot d\bmod\varphi=1$ and $1<e<\varphi$. That $e$ is uniquely defined, and the modular inverse of $d$ in the multiplicative group of integer modulo $\varphi$. For small numbers, a working method is trial and error of small odd $e>1$. A more constructive method is the (half)-extended Euclidean algorithm, which computes $e=d^{-1}\bmod \varphi$ directly. For a practical algorithm that uses only non-negative integers:
- $a\gets d\bmod \varphi$ , $b\gets \varphi$ , $x\gets0$ and $y\gets1$
Note: $a\cdot x+b\cdot y=\varphi$ will keep holding
- if $a=1$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ is $y$" and stop
- If $a=0$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ does not exist" and stop
- $r\gets\lfloor b/a\rfloor$
- $b\gets b-a\cdot r$ and $x\gets x+r\cdot y$
- if $b=1$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ is $\varphi-x$" and stop
- If $b=0$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ does not exist" and stop
- $r\gets\lfloor a/b\rfloor$
- $a\gets a-b\cdot r$ and $y\gets y+r\cdot x$
- Continue at 2
This same method is typically used to compute $d$ from $e$, since $d$ and $e$ are symmetric in $e\cdot d\bmod\varphi=1$. That's however not how $d=11$ was computed in the question; for some strange reason the question requires $e<\varphi(N)$ but not $d<\varphi(N)$, or the more usual $d<N$ or $d<\operatorname{lcm}(p-1,q-1)$.
Serious problem with this approach for RSA as practiced (thus very large $N$, at least hundreds decimal digits): It won't work, because $N$ will be so large that it can't be factored, thus $\varphi$ can't be computed in this way.
Also, the question's condition $e\cdot d\bmod\varphi(N)=1$ is a sufficient, but not a necessary condition for textbook RSA encryption using $(e,N)$ to be undone by RSA decryption using $(d,N)$, and vice versa. The necessary condition is $e\cdot d\bmod\lambda(N)=1$, where $\lambda(N)=\operatorname{lcm}(p-1,q-1)$. That condition is often used in practice: it's allowed by PKCS#1, and mandated by FIPS 186-4. Artificially small example: $N=341$, $e=7$, $d=13$ works just fine for textbook RSA encryption/decryption, yet $e\cdot d\bmod\varphi(N)=1$ does not hold (in this example $p=11$, $q=31$, $\varphi(N)=300$, $\lambda(N)=30$ ).
However, in RSA as practiced, $e$ is small, often small enough that $e$ can be found by enumeration. Thus a method could be:
- compute $c\gets2^d\bmod N$
- compute $c_2\gets c^2\bmod N$
- set $e\gets1$
- repeat
- set $e\gets e+2$
- set $c\gets c\cdot c_2\bmod N$; notice $c=2^{d\cdot e}\bmod N$
- if $c=2$
- for $m$ the first hundred odd primes (note: for small $N$, we want to stop as soon as $m^2>N$ )
- if $m^{e\cdot d}\bmod N\ne m$, continue at repeat above
- output $e$ and stop.
It's almost certain that if an $e$ is output, it's valid in the sense that textbook RSA encryption using $(e,N)$ is undone by RSA decryption using $(d,N)$, and (equivalently) $e\cdot d\bmod\lambda(N)=1$. It's not quite sure $e\cdot d\bmod\varphi(N)=1$, but knowing $e\cdot d$ and $N$ it's possible to factor $N$ (using this algorithm), and then compute the $e$ with $e\cdot d\bmod\varphi(N)=1$ and $1<e<\varphi(N)$, if for some reason that's desired.
Addition: The above is far from optimal. When $\delta=\ln(e)/\ln(N)$ is below a certain threshold, in the order of $0.292$, there are ways to factor $N$ (and thus solve the problem by the first method discussed). Basically, we swap $d$ and $e$ in Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. See there for more.
