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([I]n[/I]))^2 = 0 (mod [I]p[/I])
Where [I]n [/I]is the number to be factored, and [I]p[/I] 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 [I]p[/I], I then increment X by [I]p [/I]and repeat.

Here are the figures from a simple run:
[I]n [/I]= 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 [I]n[/I], and calculating [I]r[/I]^2 mod [I]n[/I], and repeating 100,000 times.

What am I doing wrong?

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.

[QUOTE=bsquared;317755]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. [/QUOTE]

Where do the values for [I]b [/I]come from?

sorry, b is sqrt(N)

-

[QUOTE=bsquared;317763]sorry, b is sqrt(N)[/QUOTE]
so bsquared=N

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