Not smooth enough numbers

[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?

[bsquared]

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 100-200 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.

[Sam Kennedy]

Originally Posted by bsquared

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.

Where do the values for b come from?

[bsquared]

sorry, b is sqrt(N)

[Sam Kennedy]

-

[LaurV]

Originally Posted by bsquared

sorry, b is sqrt(N)

so bsquared=N

(edit: no pun intended, we still love yafu!, the best factoring tool)