mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-06-24, 16:51   #1
Chris Card
 
Chris Card's Avatar
 
Aug 2004

22×3×11 Posts
Default 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
Chris Card is offline   Reply With Quote
Old 2005-06-24, 19:58   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11·1,039 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-06-24, 20:08   #3
Chris Card
 
Chris Card's Avatar
 
Aug 2004

22·3·11 Posts
Default

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
Chris Card is offline   Reply With Quote
Old 2005-06-25, 01:31   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354510 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2005-06-25, 09:22   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11×1,039 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-06-25, 18:44   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

22·5·587 Posts
Default

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?
ewmayer is offline   Reply With Quote
Old 2005-06-25, 19:41   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1142910 Posts
Default

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
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hiding "Advanced > Time" Iterations Jayder Information & Answers 1 2016-11-15 16:08
"Quadratic time factorization" patent mickfrancis Factoring 5 2015-02-17 14:27
"factoring" vs "factorizing" ixfd64 Factoring 4 2012-10-16 04:07
Problem / Error using the "Time..." option petrw1 PrimeNet 1 2011-07-04 17:04
Exponents to re-release for first-time testing: "harmful" errorcodes GP2 Data 4 2003-10-18 22:08

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


Thu Aug 18 19:57:14 UTC 2022 up 17:25, 1 user, load averages: 2.25, 1.83, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”