View Single Post
Old 2005-12-06, 11:23   #6
ThiloHarich's Avatar
Nov 2005

6316 Posts

We do not have to inspect all locations for (small) factors p.
If y = (ax+b)^2 - n we just have to look if the value of (ax+b) mod p is the same as one of the roots of n mod p:

For a y= (ax+b)^2 to be factorized and a factor p of the Factor base I calculate (ax+b) mod p.
For the p we have already calculated the (two) values t^2 = n mod p.
If y = t mod p we know that p divides y.
Since a,b,x were longs y mod p can be calculated fast.

This is the way I do it. Instead of calculating y/p.
I think this is what R.D. Silverman mens with resieving.

Last fiddled with by ThiloHarich on 2005-12-06 at 11:34
ThiloHarich is offline   Reply With Quote