Quote:
Originally Posted by bearnol

The time to compute 2^n + 1 mod p will be proportional to n (log p)^2
via naiive multiplication methods and n (log p loglogp logloglog p) via
FFT techniques. We only test numbers that are 1 mod 2n. From 2^x to
2^(x+1) there are 2^x/(2n) = 2^(x1)/n such numbers. Each takes
the amount of time given above. Now multiply.
I do not know where you get the exponent "13".