View Single Post
2006-04-13, 16:10   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by bearnol I've just posted the following assertion over at M+2: http://groups.google.com/group/Merse...9949e8e2560b6b Anybody feel like helping me test it? J
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".