20121109, 21:06  #1 
Oct 2012
82_{10} Posts 
Not smooth enough numbers
I've been working on implementing my own quadratic sieve program.
My problem is that I get very few, if any smooth numbers. I just wanted to make sure I was sieving correctly, here is my method: I solve the congruence (X + sqrt(n))^2 = 0 (mod p) Where n is the number to be factored, and p is a prime from the factor base (and a quadratic residue). Starting on the Xth value of my collected data, I divide out all the factors of p, I then increment X by p and repeat. Here are the figures from a simple run: n = 61063 Smoothness Bound = 100,000 Data Collection Size = 100,000 The resulting factor base size was 4792, which seems about right, however, from my data size of 100,000, I ended up with only 51 numbers which were smooth over the factor base. I collect my data by starting at the ceiling of the square root of n, and calculating r^2 mod n, and repeating 100,000 times. What am I doing wrong? Last fiddled with by Sam Kennedy on 20121109 at 21:08 
20121109, 21:31  #2 
"Ben"
Feb 2007
3,361 Posts 
You need to solve the congruence t^2 = N mod p. Then the solutions to (x + sqrt(N))^2  N = 0 mod p are x = +/t  b mod p. Then you sieve the progressions x + p, x + 2p, ... up to some bound for each solution x1, x2.
Also your smoothness bound is *way* too high. A smoothness bound of 100200 or so would be appropriate here, with a factor base of 25 or so primes. I suggest you find and read Scott Contini's thesis on the quadratic sieve which explains a lot of this stuff in pretty good detail. 
20121109, 22:14  #3 
Oct 2012
82_{10} Posts 

20121109, 22:16  #4 
"Ben"
Feb 2007
3,361 Posts 
sorry, b is sqrt(N)

20121109, 22:25  #5 
Oct 2012
2×41 Posts 

Last fiddled with by Sam Kennedy on 20121109 at 22:49 
20121110, 07:54  #6 
Romulan Interpreter
Jun 2011
Thailand
2×23×199 Posts 
so bsquared=N
(edit: no pun intended, we still love yafu!, the best factoring tool) Last fiddled with by LaurV on 20121110 at 07:55 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Special Smooth numbers  Citrix  Other Mathematical Topics  46  20120306 14:55 
Distribution of Smooth Numbers  flouran  Math  12  20091225 16:41 
Smooth and rough numbers  CRGreathouse  Math  3  20090525 05:26 
Finding smooth numbers  Citrix  Math  9  20051231 11:07 
Smooth Numbers  Yamato  Math  1  20051211 11:09 