[Sam Kennedy]

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?