Skip to main content
1 of 7
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

Wiener's result has been improved several times, and it is hard to tell how big the private exponent must be to be safe from further progress.

Further, computing $x^d\bmod n$ by proxy of $x^{d\bmod (p-1)}\bmod p$ and $x^{d\bmod (q-1)}\bmod q$ and the Chinese Remainder Theorem allows a q

if we assumed $d>n^{1/3}$ is safe enough, the technique discussed, when $x^d\bmod n$ is computed directly requires a minimum of $\lceil log_2(n)/3\rceil$ multiplications for the sparsest $d$ conceivable (a power of two), compared to say $1.2\cdot log_2(n)$ for RSA using sliding window exponentiation, thus a saving of a factor of 3.6 at most; while the

fgrieu
  • 145.5k
  • 12
  • 319
  • 611