mersenneforum.org Large Prime Variation of QS
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2012-12-17, 17:33 #1 Sam Kennedy     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?
 2012-12-17, 17:52 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT) 26·89 Posts Both relations. You also need to add the large prime to your factorbase.
 2012-12-17, 18:41 #3 jasonp Tribal Bullet     Oct 2004 23×32×72 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.
2012-12-17, 19:38   #4
Sam Kennedy

Oct 2012

8210 Posts

Quote:
 Originally Posted by jasonp 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.
What do you mean by performing the square root? Which part of the algorithm is that?

2012-12-17, 20:03   #5
Dubslow
Basketry That Evening!

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by Sam Kennedy What do you mean by performing the square root? Which part of the algorithm is that?
Taking the dependency produced by linear algebra, forming the corresponding congruence of squares modulo the factor, and then the final GCD.

 2012-12-17, 23:37 #6 Sam Kennedy     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.
2012-12-18, 07:29   #7
xilman
Bamboozled!

May 2003
Down not across

2×3×1,699 Posts

Quote:
 Originally Posted by Sam Kennedy 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.
Ah.

The traditional way is to store all the relations until you have "enough", then run a post-processing 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).

 2012-12-18, 14:03 #8 Sam Kennedy     Oct 2012 8210 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 2012-12-18 at 14:04
 2012-12-18, 14:57 #9 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT) 131008 Posts (x1^2-n)*(x2^2-n) is not equal to (x1*x2)^2-n 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?
 2012-12-18, 17:30 #10 jasonp Tribal Bullet     Oct 2004 67108 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 mickfrancis Factoring 2 2016-05-06 08:13 VBCurtis Factoring 11 2015-03-09 07:01 Carl Fischbach Miscellaneous Math 28 2010-07-20 06:54 flouran Information & Answers 6 2009-07-20 20:00 moo Software 10 2004-12-15 13:25

All times are UTC. The time now is 19:04.

Wed Aug 12 19:04:57 UTC 2020 up 26 days, 14:51, 0 users, load averages: 2.17, 2.35, 2.31

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.