mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-12-05, 17:56   #1
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

11000112 Posts
Default Factoring in the Quadratic Sieve

I have Implemented the MPQS.
After sieving you have to decomposit the generated values into the primes.
By most algorithms (i read) this is done by trial division (so do I).
This stage uses the same time as the sieving step (i have tested this only on small inputs around 40 Digits).

Which of the known factoring algorithms is recommended for this step?
ThiloHarich is offline   Reply With Quote
Old 2005-12-05, 19:30   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by ThiloHarich
I have Implemented the MPQS.
After sieving you have to decomposit the generated values into the primes.
By most algorithms (i read) this is done by trial division (so do I).
This stage uses the same time as the sieving step (i have tested this only on small inputs around 40 Digits).

Which of the known factoring algorithms is recommended for this step?
Do the factoring by resieving.

Save the locations you believe are smooth.
Resieve. Whenever you hit a location that you think is smooth,
instead of accumulating a scaled logarithm of the prime, save the prime itself.

Split the large cofactors by a 'tiny' QS that does not use the large
prime variation. Although for composites of (say) less than 60 digits,
SQUFOF will be almost as fast.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-05, 21:23   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,699 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Do the factoring by resieving.

Save the locations you believe are smooth.
Resieve. Whenever you hit a location that you think is smooth,
instead of accumulating a scaled logarithm of the prime, save the prime itself.

Split the large cofactors by a 'tiny' QS that does not use the large
prime variation. Although for composites of (say) less than 60 digits,
SQUFOF will be almost as fast.
Good advice.

Arjen Lenstra implemented and I evaluated the use of ECM to split large cofactors. It was better than SQUFOF. We never tried mini-QS.

I even tried using Fermat to split the bicomposites, just for the fun of it. Somewhat to my surprise, it worked remarkably well. It uses such fast primitives that on numbers known to have two factors of similar magnitude it's almost competitive with SQUFOF. I did, of course, employ an early-abort strategy to avoid wasting too much time on any particular cofactor.

Paul
xilman is offline   Reply With Quote
Old 2005-12-06, 09:29   #4
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

Resieving is what I actually do.
Is the QS still the best method to find the factors, even if we know that the factors have to be small?
If we have not found many factors, it makes no sense to start at sqrt (n) to find the factors.

An other question.
While sieving we have to determine a^-1 mod p, were a is the factor of the sieving polynomial (ax+b)^2 - n and p is a factor of the factor base.
I compute a^1 mod p by the extended Euclidean algorithm.
Are there faster algorithms? I heard of an unpublished paper of Richard Schroeppel. This algorithm is used in the java class BigInteger.

Back to my idea:
We can compute a^1 mod p via a^(p-2) mod p. This is only a bit slower then the extended Euclidean algorithm.
If a is 2^k then a^1 mod p = 2^k*(p-2) mod p. So we only need a fast algorithm for calculating the modulus.
In practice we need a few a's.
ThiloHarich is offline   Reply With Quote
Old 2005-12-06, 10:07   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?

Alex
akruppa is offline   Reply With Quote
Old 2005-12-06, 11:23   #6
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

6316 Posts
Default

We do not have to inspect all locations for (small) factors p.
If y = (ax+b)^2 - n we just have to look if the value of (ax+b) mod p is the same as one of the roots of n mod p:

For a y= (ax+b)^2 to be factorized and a factor p of the Factor base I calculate (ax+b) mod p.
For the p we have already calculated the (two) values t^2 = n mod p.
If y = t mod p we know that p divides y.
Since a,b,x were longs y mod p can be calculated fast.

This is the way I do it. Instead of calculating y/p.
I think this is what R.D. Silverman mens with resieving.

Last fiddled with by ThiloHarich on 2005-12-06 at 11:34
ThiloHarich is offline   Reply With Quote
Old 2005-12-06, 12:30   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by akruppa
Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?

Alex
This is what both my QS and lattice siever do. One of the algorithm
parameters is a TRIAL_DIVISION_CUTOFF. If p is smaller, I trial divide.
If larger, I resieve. This also cuts down on space requirements.

Experimentation is need to determine the best value for this cutoff; it
is implementation dependent and *strongly* depends on the speed of the
integer division hardware on one's machine.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-06, 13:19   #8
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32·11 Posts
Default

I start with the small primes as long as the y is bigger the a primitive long value. I check if ax+b is a root of n mod the small prime. If so I divide y by the prime. If y is a long value I switch to trial division.
If the y (reduced by the dividing primes) is lower the the maximal factor of the factor base, the y is a factor of the origianl y itself, and we can stop here.
ThiloHarich is offline   Reply With Quote
Old 2005-12-06, 13:52   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66418 Posts
Default

Quote:
Originally Posted by akruppa
Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?
When the number to be factored is very small (say under 100 bits) the trial factoring of sieve values takes much longer than the sieving. Resieving is a win as long as the the number of sieve values out of a sieve block needing trial factoring is large. You can skip the smaller factor base primes primes entirely during sieving and manually divide by all of them during trial factoring (after choosing a more generous trial factoring cutoff log value). Bob's QS implementation sieves with the powers of these small primes, mine doesn't sieve with them at all. Each approach has its advantages.

When the input becomes larger and the number of sieve values that need trial factoring per sieve block goes down, I've found it more efficient to skip resieving entirely. Instead you can first fill up a set of hashtables with the locations, log values and primes of every sieve update, then use the hashtable both to compute all the logs of values and to speed up trial factoring. This does mean that your sieve blocks have to be comparatively tiny, and that your siever will use a lot more memory than it has to, but it's a good compromise between sieving fast and trial factoring fast.

Once you try factoring ~60 digit composites you'll start seeing runtime differences from these techniques. Below about 50 digits everything will finish essentially instantly.

jasonp
jasonp is offline   Reply With Quote
Old 2005-12-06, 14:41   #10
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

11000112 Posts
Default

I also thought of storing the factors in a Hashmap for each location, to avoid the trial division.

But even storing even one (the highest) factor increases the sieving stage so dramatically (factor 2) that it is slower then the version with the complete trial division stage. In my implementation trial division has the same running time as sieving.
Only storing the highest factor uses just another array. Storing all factors uses much more resources (Hashmap or array) and time.
ThiloHarich is offline   Reply With Quote
Old 2005-12-07, 08:37   #11
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

11000112 Posts
Default

At the moment I have only implemented the MPQS, where the sieving interval is larger then the sieving interval in the SIQS. The sieving interval m is a few times bigger then the largest prime. So calculating a * x + b mod p might be faster then resieving.

In SIQS the sieving interval and the larges prime might be in the same area, so resieving will be fast for big factors.

For larger n a ~ sqrt (n)/m and b were no long values. But even if I calculate a * x + b mod p with arbitrary precision this is fast.

My imprecise profiling tool is telling me that sieving takes twice as long as factoring the sieved values. If I eliminate the factoring step the sieving and factoring step decreases only by 1/5.

Forget about my other idea. Calculating the mod is to slow.
Anyway how do you calculate the modular inverse?

Last fiddled with by ThiloHarich on 2005-12-07 at 08:38
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 05:27.

Fri Nov 27 05:27:51 UTC 2020 up 78 days, 2:38, 4 users, load averages: 1.41, 1.34, 1.42

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.