Sieving polynoms in Quadratic Sieve - Page 2

ThiloHarich · 2008-12-25, 19:27

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.

ThiloHarich · 2009-01-02, 08:53

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.

ThiloHarich · 2009-01-04, 18:19

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.

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	2016-05-06 08:13
Non-sieving version of Quadratic Sieve	mickfrancis	Factoring	5	2016-03-31 06:21
Finding B in Quadratic Sieve	paul0	Factoring	3	2011-09-22 17:12
Using p=2 for sieving (Quadratic sieve algorithm)	R1zZ1	Factoring	36	2007-11-02 15:59
Quadratic Sieve in wikipedia.de	ThiloHarich	Factoring	5	2006-07-14 09:51

2008-12-25, 19:27	#12
ThiloHarich Nov 2005 2²×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.

2009-01-02, 08:53	#13
ThiloHarich Nov 2005 2²·3³ Posts	If we have a sieving interval M the resulting size of the values of q(x) is in O(Msqrt (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.

2009-01-04, 18:19	#14
ThiloHarich Nov 2005 2²×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.