mersenneforum.org Not smooth enough numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2012-11-09, 21:06 #1 Sam Kennedy     Oct 2012 2·41 Posts 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 2012-11-09 at 21:08
 2012-11-09, 21:31 #2 bsquared     "Ben" Feb 2007 65248 Posts 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.
2012-11-09, 22:14   #3
Sam Kennedy

Oct 2012

10100102 Posts

Quote:
 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?

 2012-11-09, 22:16 #4 bsquared     "Ben" Feb 2007 22×853 Posts sorry, b is sqrt(N)
 2012-11-09, 22:25 #5 Sam Kennedy     Oct 2012 2×41 Posts - Last fiddled with by Sam Kennedy on 2012-11-09 at 22:49
2012-11-10, 07:54   #6
LaurV
Romulan Interpreter

Jun 2011
Thailand

5×1,877 Posts

Quote:
 Originally Posted by bsquared sorry, b is sqrt(N)
so bsquared=N

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

Last fiddled with by LaurV on 2012-11-10 at 07:55

 Similar Threads Thread Thread Starter Forum Replies Last Post Citrix Other Mathematical Topics 46 2012-03-06 14:55 flouran Math 12 2009-12-25 16:41 CRGreathouse Math 3 2009-05-25 05:26 Citrix Math 9 2005-12-31 11:07 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 03:33.

Thu Apr 22 03:33:44 UTC 2021 up 13 days, 22:14, 0 users, load averages: 1.57, 1.72, 1.79