mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-04-17, 19:10   #1
hallstei
 
hallstei's Avatar
 
Apr 2005

158 Posts
Default Quadratic Sieve - How large should the factor base be?

I am currently implementing the quadratic sieve, and was wondering how large the factor base should be.

I currently use a factor base the size of the number of bits in the number to be factored, but that doesn't seem to work too well..
hallstei is offline   Reply With Quote
Old 2005-04-17, 21:06   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by hallstei
I am currently implementing the quadratic sieve, and was wondering.
Are you aware of the wonderful and recent quadratic sieve program Msieve? There are few good reasons to write a new QS program when this one is available. See the thread Feedback for a New MPQS Utility Sought for more information, including download links.
wblipp is offline   Reply With Quote
Old 2005-04-18, 01:02   #3
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

Quote:
There are few good reasons to write a new QS program when this one is available.
Lots of people write their own implementation because its a good way to learn the nuts and bolts of the algorithm. Its one thing to read how it works, its another to work out all the details and make it work. I did a similar thing a couple years ago to help learn it.
ColdFury is offline   Reply With Quote
Old 2005-04-18, 01:42   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67168 Posts
Default

Quote:
Originally Posted by hallstei
I am currently implementing the quadratic sieve, and was wondering how large the factor base should be.

I currently use a factor base the size of the number of bits in the number to be factored, but that doesn't seem to work too well..
The "best" factor base size is a function of the implementation, the size of the input, and the exact number being factored. Asymptotically you can show using a little calculus that making the largest factor base prime ~exp(0.5*log(n)*log(log(n))) is optimal, where n is being factored and log is a natural logarithm. Rigorously using this value will give you a factor base far larger than is common for QS programs.

The literature doesn't help either; one of the early 2LP QS papers recommends a FB size of ~4000 for a 90-digit factorization, where msieve uses a FB of over 60000 for numbers that size! I suppose the size of 4000 is fine if you have a cray...

Most programs just tabulate values that appear to be optimal across a wide range of emprical tests. Some programs attempt to give an overall formula and then tailor it to the number being factored; for example, the Miracl factoring utility sets the number of FB entries to (digits^4)/4096, adds some fudge, then finds that many primes given the exact value of n. The good news is that QS seems pretty forgiving of a bad choice of FB size, unless the chosen size is grossly too large or too small (yours is definitely too small, though for inputs < ~100 bits it's okay if you're using multiple polynomials).

BTW, msieve started off as a learning tool as well. There's just something about QS that made me want to optimize the dickens out of it

jasonp
jasonp is offline   Reply With Quote
Old 2005-04-19, 08:57   #5
hallstei
 
hallstei's Avatar
 
Apr 2005

158 Posts
Default

Quote:
Originally Posted by jasonp
The "best" factor base size is a function of the implementation, the size of the input, and the exact number being factored. Asymptotically you can show using a little calculus that making the largest factor base prime ~exp(0.5*log(n)*log(log(n))) is optimal, where n is being factored and log is a natural logarithm. Rigorously using this value will give you a factor base far larger than is common for QS programs.

The literature doesn't help either; one of the early 2LP QS papers recommends a FB size of ~4000 for a 90-digit factorization, where msieve uses a FB of over 60000 for numbers that size! I suppose the size of 4000 is fine if you have a cray...

Most programs just tabulate values that appear to be optimal across a wide range of emprical tests. Some programs attempt to give an overall formula and then tailor it to the number being factored; for example, the Miracl factoring utility sets the number of FB entries to (digits^4)/4096, adds some fudge, then finds that many primes given the exact value of n. The good news is that QS seems pretty forgiving of a bad choice of FB size, unless the chosen size is grossly too large or too small (yours is definitely too small, though for inputs < ~100 bits it's okay if you're using multiple polynomials).

BTW, msieve started off as a learning tool as well. There's just something about QS that made me want to optimize the dickens out of it

jasonp

That is right, I implement this program just to learn the algorithm. Thanks for the feedback, Jason! I'm now trying bit size^2, to see how that works out.

The main obstacle for me at the moment seems to be the 'block Lanczos' algorithm which, it appears, is THE method for finding a perfect square from the relations. From what I have found on the Internet it seems extremely complex and mathematically difficult. Anyone know where I can find a good explanation of this algorithm?

Cheers,

Hallstein
hallstei is offline   Reply With Quote
Old 2005-04-19, 11:58   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by hallstei
The main obstacle for me at the moment seems to be the 'block Lanczos' algorithm which, it appears, is THE method for finding a perfect square from the relations. From what I have found on the Internet it seems extremely complex and mathematically difficult. Anyone know where I can find a good explanation of this algorithm?
There isn't one. If you want to build a block Lanczos solver, you basically have to find someone else's code, have Montgomery's original paper in your lap, and keep debugging until both codes can find a nullspace of the same matrix.

Another possibility is Gauss elimination; with one large prime, GE can solve matrices from factorizations up to ~70 digits without much trouble. There's a huge literature on sparse GE, though most of it is not written with factoring in mind. Older versions of msieve used GE, and I can send the source for it if that will help.

jasonp
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
primitive roots- when the base is a quadratic algebraic integer devarajkandadai Number Theory Discussion Group 0 2018-02-08 05:15
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Factoring in the Quadratic Sieve ThiloHarich Factoring 47 2007-01-08 14:12
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 09:41.

Tue Jan 19 09:41:47 UTC 2021 up 47 days, 5:53, 0 users, load averages: 1.48, 1.86, 2.15

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.