New answers tagged


By using the binary expansion of an exponent $t$ and repeated squaring you can compute $x^t$ modulo $n$ with $O(\log n)$ modulo $n$ multiplication operations. And each modulo $n$ multiplication and division will take $O(\log^2 n)$ integer operations. So this makes $O(\log^3 n)$ integer operations. Once you have $x^t$ modulo $n,$ then $x^{2t},x^{4t},x^{2^st}$ ...

Top 50 recent answers are included