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
