20121217, 17:33  #1 
Oct 2012
2·41 Posts 
Large Prime Variation of QS
I've started working on the large prime variation of the quadratic sieve, I wasn't sure, once you have found two relations with the same cofactor, do you add both relations to your list of relations, or the product of the relations?

20121217, 17:52  #2 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
13075_{8} Posts 
Both relations. You also need to add the large prime to your factorbase.

20121217, 18:41  #3 
Tribal Bullet
Oct 2004
3,527 Posts 
You need to account for the large prime when performing the square root (it's part of the relation), but you don't need to add large primes to the factor base.

20121217, 19:38  #4 
Oct 2012
2·41 Posts 

20121217, 20:03  #5 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 

20121217, 23:37  #6 
Oct 2012
2×41 Posts 
What needs to be done differently? At the minute I'm simply adding the factor to the factor base, and I've already seen a significant speed increase, but if I could avoid doing that it would also help.
I thought because both partial relations will have a 1 in the same column, you can add them both to the relations list/matrix without any problems, however the code didn't work until I added the number to the factor base. 
20121218, 07:29  #7  
Bamboozled!
May 2003
Down not across
2^{2}·3·7·11^{2} Posts 
Quote:
The traditional way is to store all the relations until you have "enough", then run a postprocessing pass which repeatedly finds the large primes which occur only once in the entire set and discards the corresponding relations. After this is complete, all large primes are guaranteed to occur at least twice. Relations containing a particular large prime are multiplied together pairwise (i.e. multiplying the residues and merging the two lists of primes). 

20121218, 14:03  #8 
Oct 2012
2×41 Posts 
So say you have two relations:
x1^2 = a * p x2^2= b * p You then store the product in the list of full relations: x1 * x2 and: a * p * b * p Last fiddled with by Sam Kennedy on 20121218 at 14:04 
20121218, 14:57  #9 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
5,693 Posts 
(x1^2n)*(x2^2n) is not equal to (x1*x2)^2n
The way I did it was to record a list of the large primes I had found and at what x. When I found it again I added the prime to the factorbase and the two relations to the normal set of relations. When I find it for a third time it just gets added etc. @Jasonp Do you keep all the large primes in a separate list and eliminate them before doing linear algebra or something? Are you assuming you will only find each large prime twice? 
20121218, 17:30  #10 
Tribal Bullet
Oct 2004
3527_{10} Posts 
The QS code in Msieve always assumes relations have two large primes, and adds the large primes to the graph structure that counts the number of matrix columns that are available. If relations only ever have one large prime this is overkill.
Large primes never are added to the factor base; relations only need to remember which large primes they have, and when multiplying relations together to form a dependency the large primes are counted separately from the factor base primes. You can handle the accounting in different ways, this was just what was convenient. As long as both sides of the final congruence contain the correct factors it doesn't matter how they're represented internally. 
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 
29 to 30 bit large prime SNFS crossover  VBCurtis  Factoring  11  20150309 07:01 
The Fischbach Prime a mersenne variation  Carl Fischbach  Miscellaneous Math  28  20100720 06:54 
Integral Variation  flouran  Information & Answers  6  20090720 20:00 
Putting prime 95 on a large number of machines  moo  Software  10  20041215 13:25 