mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Large Prime Variation of QS (https://www.mersenneforum.org/showthread.php?t=17574)

 Sam Kennedy 2012-12-17 17:33

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?

 henryzz 2012-12-17 17:52

Both relations. You also need to add the large prime to your factorbase.

 jasonp 2012-12-17 18:41

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.

 Sam Kennedy 2012-12-17 19:38

[QUOTE=jasonp;321914]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.[/QUOTE]

What do you mean by performing the square root? Which part of the algorithm is that?

 Dubslow 2012-12-17 20:03

[QUOTE=Sam Kennedy;321920]What do you mean by performing the square root? Which part of the algorithm is that?[/QUOTE]

Taking the dependency produced by linear algebra, forming the corresponding congruence of squares modulo the factor, and then the final GCD.

 Sam Kennedy 2012-12-17 23:37

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.

 xilman 2012-12-18 07:29

[QUOTE=Sam Kennedy;321936]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.[/QUOTE]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).

 Sam Kennedy 2012-12-18 14:03

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

 henryzz 2012-12-18 14:57

(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?

 jasonp 2012-12-18 17:30

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.

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