# Tag Info

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 ... 1 The first (and hardest) step is to factor$n$; the easiest way to do this (given$e$and$d$) is with this randomized procedure: Select a random value$z$from the range$(2, n-2)$Compute the value$\lambda = (ed-1)/2^k$, where$k$is that integer that makes$\lambda$an odd integer. Compute$t = z^\lambda \bmod n$. If$t = 1$or$t = n-1\$, we fail on ...