View Single Post
Old 2012-11-09, 21:31   #2
bsquared's Avatar
Feb 2007

41×83 Posts

You need to solve the congruence t^2 = N mod p. Then the solutions to (x + sqrt(N))^2 - N = 0 mod p are x = +/-t - b mod p. Then you sieve the progressions x + p, x + 2p, ... up to some bound for each solution x1, x2.

Also your smoothness bound is *way* too high. A smoothness bound of 100-200 or so would be appropriate here, with a factor base of 25 or so primes.

I suggest you find and read Scott Contini's thesis on the quadratic sieve which explains a lot of this stuff in pretty good detail.
bsquared is offline   Reply With Quote