Return to Answer

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.
As Maarten points out in the comments below this attack is very fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

1. Set $c_m \gets (c * c) \bmod n$,
2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
3. Set $c_3 \gets (c * c_m) \bmod n$
4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.
As Maarten points out in the comments below this attack is very fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

1. Set $c_m \gets (c * c) \bmod n$,
2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
3. Set $c_3 \gets (c * c_m) \bmod n$
4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e>2^{40}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

1. Set $c_m \gets (c * c) \bmod n$,
2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
3. Set $c_3 \gets (c * c_m) \bmod n$
4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.
As Maarten points out in the comments below this attack is very fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

1. Set $c_m \gets (c * c) \bmod n$,
2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
3. Set $c_3 \gets (c * c_m) \bmod n$
4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e>2^{40}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=1$):

1. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
2. Set $c_{i+1}\gets (c_i*m) \bmod n$, goto step 1

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e>2^{40}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

1. Set $c_m \gets (c * c) \bmod n$,
2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
3. Set $c_3 \gets (c * c_m) \bmod n$
4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.