20070227, 16:34  #1 
Feb 2007
5 Posts 
Using p=2 for sieving (Quadratic sieve algorithm)
Hi guys,
I'm trying to implement the Quadratic Sieve algorithm (MPQS) and I don't know how to use p=2 in sieving, because I noticed that without this prime in factor base I have not enough Bsmooth relations and my algorithm is too much slow. The problem is that the Hensel Lemma doesn't hold with p=2. Thanks in advance 
20070227, 16:59  #2  
Tribal Bullet
Oct 2004
DE3_{16} Posts 
Quote:
jasonp 

20070227, 17:52  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Dear Jason,
does Msieve sieve with powers of small primes, i.e. sieve with p^k > 30 even though p<30 ? If yes, does doing vs. not doing it have an appreciable effect on yield? Thanks, Alex 
20070227, 18:15  #4  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
Before one sieves, one initializes an array to 0. As part of the initialization procedure, one can simply set the relevant bytes in this array to log 2 [scaled, of course] instead of 0. This takes no extra time. 

20070227, 18:25  #5  
Tribal Bullet
Oct 2004
3^{2}×5×79 Posts 
Quote:
The 'pad' of 30 was chosen so that the yield found in a few test factoizations came out to be about the same as the yield when small primes are not skipped. I wouldn't be surprised if more tuning was needed; the decision was made years ago and msieve is very different now. The bound of 256 is a lot larger than is usual for the small prime variation; it had to be that big because trial division by primes < 2^17 uses integer reciprocals, and the reciprocal values could not be computed for the small primes and still fit in 32 bits. Profiling shows that the smallest primes never take more than 10% of the total runtime (this tends to 0% for factorizations above about 70 digits), so it's okay to be conservative and test lots of sieve values. Currently about 1/3 of the sieve values making the first cutoff also make the second cutoff. The NFS code uses resieving, and in that case it's important that as few relations as possible survive the log cutoff. Switching sieve roots is also easy, thus the NFS code sieves with all p^k for p^k < 1400 jasonp 

20070227, 19:05  #6  
Feb 2007
5 Posts 
Quote:
Can you approximately indicate me how much i have to increase the cutoff to compensate avoiding of all primes smaller than 30? Last fiddled with by R1zZ1 on 20070227 at 19:07 

20070228, 01:13  #7  
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Quote:
However, I don't think you should use the smart way. What you want is the average contribution to a random *smooth* sieve value, and these contain a higher proportion of small p compared to random sieve values. Nobody has looked seriously at approximating this, so in the end it likely is preferable to decide on the amount of 'padding' by experiment. Good luck, jasonp 

20070302, 21:59  #8 
Feb 2007
5_{16} Posts 
YES! Thank you for helping me and my group to do this very very interesting project! I've founded a lot of interesting threads on this forum that helped us to do a good implementation of quadratic sieve algorithm.
Now my mpqs implementation works and i was able to factorize 40+ digits very fast. The bottleneck is linear algebra solved with matker of pari/gp library: 10 minutes for ~1500 relations... Hence I'm forced to maintain the limit of factor base (B) very small to have a little number of relations and speed up linear algebra phase. Any ideas to solve this without implementing block lanczos myself (probably too much hard for my capabilities) and so factorize more digits faster? This project is for university course of number theory held by René Schoof at University of Tor Vergata, Rome (Computer Engineer). My teacher is famous, do you know him? http://www.mat.uniroma2.it/~schoof/ Last fiddled with by R1zZ1 on 20070302 at 22:26 
20070302, 23:42  #9  
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Quote:
jasonp 

20070911, 19:59  #10  
Sep 2007
2^{2}×3 Posts 
Quote:
Can you please help me with an example? Let's suppose that my (60digit) n is = 340282366920938463463300000000009999999999974607431768211457, then the primes < 30 in my FB are 1 2 23 29. Furthermore I extimated that P(=#FB)=3000 and M=300'000 Which cutoff for searching smooth relations would you advise in this case? Is it possible to put it in a formula (eg: log (M*sqrt(N))+??) or otherwise how would you suggest to calculate the padding? thanks really a lot!bye 

20070911, 20:58  #11  
"Ben"
Feb 2007
2^{2}·3·311 Posts 
Quote:
First a comment: The size of your FB (3000) and M seem small, at least compared with what my implementation uses. But from everything I've read, these can be very implementation specific. If I force mine to use your values, it is about 2x slower. The small prime pad I get from trial sieving a couple blocks using only the small primes in the FB (i.e. < 50), and finding the average and standard deviation afterwards and adding them together to get the pad (in bits). (I read this method somewhere). It seems to work ok, but it also doesn't change much and so is probably not necessary. 

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  20160506 08:13 
Nonsieving version of Quadratic Sieve  mickfrancis  Factoring  5  20160331 06:21 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Sieving polynoms in Quadratic Sieve  ThiloHarich  Factoring  13  20090104 18:19 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 