mersenneforum.org DJB paper "Factoring into coprimes in essentially linear time"
 Register FAQ Search Today's Posts Mark Forums Read

 2005-06-24, 16:51 #1 Chris Card     Aug 2004 100000102 Posts DJB paper "Factoring into coprimes in essentially linear time" Hi All, I just came across this paper from Berstein in "Journal of Algorithms" Here's the link: http://www.sciencedirect.com/science.../sdarticle.pdf Can anyone tell me if this algorithm is practical for use in an NFS siever for doing the final factorisation of the candidate smooth norms? From a quick scan through, the algorithm seems to depend on first calculating the product of all the norms. Does an implementation have to make use of special tricks, like use of FFT for the multiplication, in order to be practical? Chris
2005-06-24, 19:58   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2×112×47 Posts

Quote:
 Originally Posted by Chris Card From a quick scan through, the algorithm seems to depend on first calculating the product of all the norms. Does an implementation have to make use of special tricks, like use of FFT for the multiplication, in order to be practical?
Got it in one.

Dan's algorithm has been kicking around for some time now. It works well if memory is free, or nearly so, and if you have a lot of numbers for which you want the small factors. The latter is certainly the case in NFS.

Paul

2005-06-24, 20:08   #3
Chris Card

Aug 2004

2·5·13 Posts

Quote:
 Originally Posted by xilman Got it in one.
Damn! that means I'm actually going to have to understand that stuff now ...
Is it used in any current NFS implementations?

Quote:
 Originally Posted by xilman Dan's algorithm has been kicking around for some time now.
Yes, I noticed that the paper was submitted in 1998, but only just got published!

Chris

2005-06-25, 01:31   #4
jasonp
Tribal Bullet

Oct 2004

5·709 Posts

Quote:
 Originally Posted by Chris Card From a quick scan through, the algorithm seems to depend on first calculating the product of all the norms. Does an implementation have to make use of special tricks, like use of FFT for the multiplication, in order to be practical?
I seriously thought about implementing this, but instrumenting my siever code showed that an enormous pile of sieve values survive to the trial factoring stage only to get weeded out (many thousands of sieve values for every surviving relation). I just have a hard time believing that it would be more efficient to skip the trial factoring (which only takes about 2-4% of the runtime in my implementation once the factorization is big enough) and instead do FFTs on numbers tens of millions of digits in size. Maybe that would change if you looked for three large primes instead of two.

I get the same feeling about Bernstein's other similar idea, that you can take all of your unfactored relations and find the core set of them with repeated small factors, without actually performing any factorizations. If you need 500 million relations, and have to sift through thousands of times that number, you'd end up having to perform FFTs on a dataset that won't even fit on a hard drive.

Somebody tell me if I have the scale wrong here.

jasonp

Last fiddled with by jasonp on 2005-06-25 at 01:42

2005-06-25, 09:22   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2×112×47 Posts

Quote:
 Originally Posted by jasonp I get the same feeling about Bernstein's other similar idea, that you can take all of your unfactored relations and find the core set of them with repeated small factors, without actually performing any factorizations. If you need 500 million relations, and have to sift through thousands of times that number, you'd end up having to perform FFTs on a dataset that won't even fit on a hard drive. Somebody tell me if I have the scale wrong here.
You've got it slightly wrong, I believe. As I understand it, the product tree of small primes should be about the same size as the product of the unfactored relations. However, with a reasonable sized factorbase, the numbers are unlikely to fit in RAM. That was my conclusion when I investigated the algorithm, including a couple of noddy implementations, a few years ago.

When I told Dan that his algorithm seemed to be correct but required infeasible amounts of memory, he replied that the product tree, or portions thereof, could reside on disk without changing the asyptotic behaviour. Again, correct but now the proportionality constant grows substantially.

The algorithm may yet prove practical but without a working implementation I remain doubtful.

Paul

 2005-06-25, 18:44 #6 ewmayer ∂2ω=0     Sep 2002 Repรบblica de California 23·32·163 Posts This idea of completely ignoring memory access time when estimating algorithmic complexity seems somewhat bogus to me. Reading and writing memory takes CPU time, so if memory usage winds up being the bottleneck of the algorithm in question and the memory usage is not linear, well, then neither is the algorithm. If I understand Bernstein properly (the memory estimates are buried pretty deep amongst all the neat-o newfangled acronyms) the resulting complexity estimate for his algorithm would still be subquadratic (specifically n*log n), but not linear as he claims. Am I reading things correctly?
2005-06-25, 19:41   #7
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2C6E16 Posts

Quote:
 Originally Posted by ewmayer ... newfangled acronyms) the resulting complexity estimate for his algorithm would still be subquadratic (specifically n*log n), but not linear as he claims. Am I reading things correctly?
Yes and no. If memory is slowed down by a constant amount, the asymptotics remain the same. If memory access scales as a function of n then it indeed must be taken into account.

Assuming memory access time of O(1) then I believe that Dan's claim is true: factoring in essentially linear time.

Paul

 Similar Threads Thread Thread Starter Forum Replies Last Post Jayder Information & Answers 1 2016-11-15 16:08 mickfrancis Factoring 5 2015-02-17 14:27 ixfd64 Factoring 4 2012-10-16 04:07 petrw1 PrimeNet 1 2011-07-04 17:04 GP2 Data 4 2003-10-18 22:08

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

Thu Jun 30 11:19:33 UTC 2022 up 77 days, 9:20, 0 users, load averages: 1.29, 1.32, 1.31