Thread: Not smooth enough numbers View Single Post
 2012-11-09, 21:06 #1 Sam Kennedy     Oct 2012 10100102 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 2012-11-09 at 21:08