20051205, 17:56  #1 
Nov 2005
101 Posts 
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? 
20051205, 19:30  #2  
Nov 2003
1110100100100_{2} Posts 
Quote:
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. 

20051205, 21:23  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
29×367 Posts 
Quote:
Arjen Lenstra implemented and I evaluated the use of ECM to split large cofactors. It was better than SQUFOF. We never tried miniQS. 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 earlyabort strategy to avoid wasting too much time on any particular cofactor. Paul 

20051206, 09:29  #4 
Nov 2005
101 Posts 
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^(p2) 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*(p2) mod p. So we only need a fast algorithm for calculating the modulus. In practice we need a few a's. 
20051206, 10:07  #5 
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
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 
20051206, 11:23  #6 
Nov 2005
101 Posts 
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 20051206 at 11:34 
20051206, 12:30  #7  
Nov 2003
1110100100100_{2} Posts 
Quote:
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. 

20051206, 13:19  #8 
Nov 2005
101 Posts 
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. 
20051206, 13:52  #9  
Tribal Bullet
Oct 2004
110111010000_{2} Posts 
Quote:
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 

20051206, 14:41  #10 
Nov 2005
101 Posts 
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. 
20051207, 08:37  #11 
Nov 2005
101 Posts 
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 20051207 at 08:38 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 