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 100200 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) 
All times are UTC. The time now is 10:58. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.