20081225, 19:27  #12 
Nov 2005
2^{2}×3^{3} Posts 
Of coarse we have to calculate \floor{q_i^2} mod N to determine the factors over the factor base. The squaring is very time consuming.
Maybe we can improve here if we do some restrictions. 
20090102, 08:53  #13 
Nov 2005
2^{2}·3^{3} Posts 
If we have a sieving interval M the resulting size of the values of q(x) is in O(M*sqrt (N)).
For QS M is O(exp (sqrt (log (N) * log log (N))) and the values were bounded by O(N). So I expect the running time to be decreased only by an constant factor in the exponent (something like sqrt (2)), which is far away from the NFS. But for the CFRAC the same should hold as well?? I'm going to implement it. I already have a MPQS in place so lets see how it will be compared with it. 
20090104, 18:19  #14 
Nov 2005
2^{2}×3^{3} Posts 
The answer to my first question is rather simple if q(x) is getting greater then N we have to reduce it by applying mod N on the result. But then we can not be sure that 'a' still divides q(x), so we have to limit M. and choose different a's.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve  mickfrancis  Factoring  2  20160506 08:13 
Nonsieving version of Quadratic Sieve  mickfrancis  Factoring  5  20160331 06:21 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Using p=2 for sieving (Quadratic sieve algorithm)  R1zZ1  Factoring  36  20071102 15:59 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 