mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-12-17, 17:33   #1
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2×41 Posts
Default 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?
Sam Kennedy is offline   Reply With Quote
Old 2012-12-17, 17:52   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131328 Posts
Default

Both relations. You also need to add the large prime to your factorbase.
henryzz is offline   Reply With Quote
Old 2012-12-17, 18:41   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DC916 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2012-12-17, 19:38   #4
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2×41 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
Sam Kennedy is offline   Reply With Quote
Old 2012-12-17, 20:03   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by Sam Kennedy View Post
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.
Dubslow is offline   Reply With Quote
Old 2012-12-17, 23:37   #6
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2·41 Posts
Default

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.
Sam Kennedy is offline   Reply With Quote
Old 2012-12-18, 07:29   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·32·569 Posts
Default

Quote:
Originally Posted by Sam Kennedy View Post
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).
xilman is offline   Reply With Quote
Old 2012-12-18, 14:03   #8
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2·41 Posts
Default

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
Sam Kennedy is offline   Reply With Quote
Old 2012-12-18, 14:57   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,861 Posts
Default

(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?
henryzz is offline   Reply With Quote
Old 2012-12-18, 17:30   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

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 2016-05-06 08:13
29 to 30 bit large prime SNFS crossover VBCurtis Factoring 11 2015-03-09 07:01
The Fischbach Prime a mersenne variation Carl Fischbach Miscellaneous Math 28 2010-07-20 06:54
Integral Variation flouran Information & Answers 6 2009-07-20 20:00
Putting prime 95 on a large number of machines moo Software 10 2004-12-15 13:25

All times are UTC. The time now is 11:20.

Tue Sep 22 11:20:36 UTC 2020 up 12 days, 8:31, 0 users, load averages: 1.49, 1.26, 1.30

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.