View Single Post
Old 2006-04-13, 16:10   #2
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by bearnol
I've just posted the following assertion over at M+2:
Anybody feel like helping me test it?
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^(x-1)/n such numbers. Each takes
the amount of time given above. Now multiply.

I do not know where you get the exponent "13".
R.D. Silverman is offline   Reply With Quote