mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-06-23, 16:11   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×13×113 Posts
Default QS question

Currently in the quadratic sieve we sieve until we have a number of relations slightly above the number of primes in the factorbase. In nfs, however, we try postprocessing at regular intervals hoping that enough of the primes aren't used. Would it make sense to try some method like the one we use in nfs for qs? Do we have any knowledge of how many primes are not used in an average matrix from qs?
henryzz is offline   Reply With Quote
Old 2011-06-23, 17:21   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

The existing QS programs sieve until the exact point where a matrix is possible because using two large primes lets you treat the computation of the cutoff point as an easy graph problem, that can be solved as relations are added. This, plus the fact that the linear algebra is never a bottleneck for QS, means that it isn't worth doing oversieving to try to make the matrix take less time.

Once you move to QS with more than two large primes in the sieving, it's not straightforward anymore to compute the exact finishing point incrementally, so in that case you have little choice but to do 'test filtering' until a matrix can be formed. The payoff is that with three large primes the sieving is faster, so the total time will hopefully be less even with the messier postprocessing.

Actually, as long as you get the input dataset into a canonical format, filtering and linear algebra for QS and NFS can be made to look exactly the same. All the tricks we use to build a good NFS matrix can be scaled down to build a good QS matrix.

Per your statement above, we are actually looking for a dataset where the number of relations remaining exceeds by a specified amount the number of primes remaining, after useless copies of both are removed. I would think the statistics of QS and NFS datasets are identical if the same filtering techniques are used on each; the only reason we don't know for sure is that QS would have to sieve for a very long time to form a matrix as big as even a small NFS factorization (~100 digits) produces regularly.

Last fiddled with by jasonp on 2011-06-23 at 17:28
jasonp is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 13:43.


Fri Jun 25 13:43:34 UTC 2021 up 28 days, 11:30, 1 user, load averages: 1.60, 1.46, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.