Factor 2^1061-1

[LaurV]

@axn:
First part is plain clear. As usual, you are right, and I was overseeing some "small details", this time it was related to exponentiation algorithm.

But here you lost me:

Originally Posted by axn

As far as not reversing FFT -- you don't do the inverse FFT because you have to sub the 2. You do it because, after the squaring, you don't have enough bits left in the FFT limbs to do on more squaring.

BTW, Technically you can do the subtraction without doing the inverse FFT -- it's just not cost effective.

I was thinking that we do the IFT to control the errors. I know we can subtract 2 without making IFT (don't know how, if you ask me to do it by pencil, but I know we can, the subject was debated here on the forum before, and I have read about it). But the part with "not enough bits in the FFT limbs", here you lost me, for sure... I will check about it.

[Christenson]

@LaurV:
Subtracting 2 in the FFT space is as simple as subtracting, termwise, FFT(2) from the FFT you are about to do the inverse FFT on. But FFT(2) contains many nonzero terms (as many as the length of the FFT), so is relatively expensive to subtract in FFT space instead of just subtracting 2 and doing a few carries after the IFFT in normal digit space.

The economics, of course, would be different if we were subtracting something that had lots of digits and and didn't have inordinately more nonzero terms in the FFT than in the original.

[dmd]

mtf()=
{
local(M:int);
local(a,t);
forprime(p=2, 5000,
 M= (2^p-1):int;
 a= Mod(3,M);
 t= polrootsmod(a^2 - a*X + X^2, M);
 if(#t==2, print(p))
)
};

see http://dxdy.ru/post515377.html#p515377