mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-11-09, 21:06   #1
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2×41 Posts
Default 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
Sam Kennedy is offline   Reply With Quote
Old 2012-11-09, 21:31   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×859 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2012-11-09, 22:14   #3
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

10100102 Posts
Default

Quote:
Originally Posted by bsquared View Post
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?
Sam Kennedy is offline   Reply With Quote
Old 2012-11-09, 22:16   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·859 Posts
Default

sorry, b is sqrt(N)
bsquared is offline   Reply With Quote
Old 2012-11-09, 22:25   #5
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2·41 Posts
Default

-

Last fiddled with by Sam Kennedy on 2012-11-09 at 22:49
Sam Kennedy is offline   Reply With Quote
Old 2012-11-10, 07:54   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25·5·59 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Special Smooth numbers Citrix Other Mathematical Topics 46 2012-03-06 14:55
Distribution of Smooth Numbers flouran Math 12 2009-12-25 16:41
Smooth and rough numbers CRGreathouse Math 3 2009-05-25 05:26
Finding smooth numbers Citrix Math 9 2005-12-31 11:07
Smooth Numbers Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 19:30.

Thu May 6 19:30:16 UTC 2021 up 28 days, 14:11, 0 users, load averages: 2.66, 2.20, 2.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.