Finding public exponent e I'm trying to create an algorithm to find the public exponent e given a plain (non-CRT) private key that doesn't include the public exponent, i.e. I've only got $n$ and $d$.

A question has already been asked how easy it would be to find the public key given a private key. The answer was that it was likely to be easier, but none of the answers specify a good algorithm for RSA.

What would be the most efficient algorithm for finding the public exponent for RSA given the private key?
The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1&lt;m&lt;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&lt;\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&lt;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):


Set $c_m \gets (c * c) \bmod n$,
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.
Set $c_3 \gets (c * c_m) \bmod n$
Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
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:


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