Researcher Modifies Sieve of Eratosthenes To Work With Less Physical Memory Space (scientificamerican.com) 78
grcumb writes: Peruvian mathematician Harald Helfgott made his mark on the history of mathematics by solving Goldbach's weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three prime numbers. Now, according to Scientific American, he's found a better solution to the sieve of Eratosthenes: "In order to determine with this sieve all primes between 1 and 100, for example, one has to write down the list of numbers in numerical order and start crossing them out in a certain order: first, the multiples of 2 (except the 2); then, the multiples of 3, except the 3; and so on, starting by the next number that had not been crossed out. The numbers that survive this procedure will be the primes. The method can be formulated as an algorithm." But now, Helfgott has found a method to drastically reduce the amount of RAM required to run the algorithm: "Now, inspired by combined approaches to the analytical 100-year-old technique called the circle method, Helfgott was able to modify the sieve of Eratosthenes to work with less physical memory space. In mathematical terms: instead of needing a space N, now it is enough to have the cube root of N." So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks? Mathematician Jean Carlos Cortissoz Iriarte of Cornell University and Los Andes University offers an analogy: "Let's pretend that you are a computer and that to store data in your memory you use sheets of paper. If to calculate the primes between 1 and 1,000,000, you need 200 reams of paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need one fifth of a ream (about 100 sheets)," he says.
What's the _actual_ algorithm. (Score:4, Insightful)
*sigh*
Getting tired of "news" posting _zero_ details.
Does anyone have details on the actual algorithm? Reference Implementation?
Re: (Score:2)
Re: (Score:1)
200 million 32-bit primes in about 100 megabytes of space
That is not 40:1, that is 8:1. Moreover, I looked at your source code - that is so non-portable, my toes cringe when thinking of porting it to e.g. Linux or Solaris. Even if that thing is somewhat of a technical feat, 8:1 compression ratios on pure numbers can be obtained with much less code and much less complexity.
Re: (Score:3)
I already read the link a few hours before it was posted. There was zero details on the algorithm and no link to the actual research that I could see.
Re:What's the _actual_ algorithm. (Score:5, Informative)
I already read the link a few hours before it was posted. There was zero details on the algorithm and no link to the actual research that I could see.
Well, in case you are interested, after checking around, it appears that this "algorithm" was a minor result of Mr. Helfgott's work to prove the ternary Goldbach conjecture (every odd integer n greater than 5 is the sum of three primes). Here's the preprint of the paper [arxiv.org], I should warn you that it appears to be a very theoretical paper, one targetted at the Goldbach conjecture (not practical prime sieving), so there is not a fully fleshed out algorithm that you can translate into a computer program. I haven't gone through the paper in detail, but it appears to rely heavily on technique from a Messr. Ramare.
We start by adapting ideas from Ramare’s version of the large sieve for primes to estimate l2 norms over parts of the circle. We are left with the task
of giving an explicit bound on the factor in Ramare’s work. As a side effect, this finally gives a fully explicit large sieve for primes that is asymptotically optimal, meaning a sieve that does not have a spurious factor of exp(gamma) in front; this was an arguably important gap in the literature.
I cannot find a definitive paper about this technique, but is appears to be related to this earlier paper [univmrs.fr]. Mr. Helfgott apparently just tightening the bounds which theoretically should create a better sieve algorithm. My impression is that I think it will take some concerted effort to create a computer algorithm out of this algorithm.
However, your mileage may vary...
Re: (Score:2)
Since the prime sieve is generally an array of bits the first (obvious) compression is to skip past 2 (and 3?) then you only need to maintain a bit pattern that represents every other bit, or possibly every 3rd bit ... generalizing this pattern means with the sum of 3 primes pattern implies that you exchange the bit pattern for some lookup table that indicates which primes this bit represents? Not sure ..
At some point the bit field (sieve) gets pretty sparse, sparse enough that hold an array of primes and/o
Re: (Score:2)
The paper you point to proves that all add numbers larger than 10^27 are the sum of three primes and then references another paper where they have tested all odd numbers to 10^38 and concludes that all odd numbers larger than 5 can be the sum of 3 primes. It does not say anything about the Sieve of Eratosthenes. So, as far as I can tell there is nothing describing the modifications.
Re: (Score:2)
Also:
So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks?
No.
And that's not just applying Betteridge's Law. The answer really is "no", even if someone manages to turn it into a simple algorithmic implementation.
Re: (Score:2)
See my post below. Prof. Helgott did a presentation at the Buenos Aires conference, he's working on putting up a preprint. Stop whining.
Re: (Score:3)
Yeah, I was disappointed not to see his method too.
Patent Pending? Classified by intelligence services? BS?
Re-reading the subtitle is does say "COULD accelerate computer calculations"
It doesn't say "accelerates computer calculations"
Still to be proven and inconclusive?
...and they details they do post are wrong (Score:5, Insightful)
Getting tired of "news" posting _zero_ details.
I'd be happier if the meagre details they do post were at least correct. If one fifth of a ream is 100 sheets then 200 reams is 100,000 sheets not 10,000 as the summary states.
Re: (Score:3)
Helfgott has not (yet) published his paper. The only thing I could find was an abstract, in Spanish. [dm.uba.ar]. He works at the University of Göttingen, and so probably knows basic German. Me speaking German, I'm going to gently ask him for his paper by email.
Re: (Score:2)
Update Prof. Helfgott has kindly replied to my email inquiry, promising to signal me as soon as he's put a preprint up. If you're interested, ping me.
Re: (Score:2)
Awesome! Thanks for the update.
Are you able to post his email address so I can directly email him too ?
I'd rather not provide contact details on /. for obvious reasons (I guess I could make a throwaway reddit account if push comes to shove.)
Re: (Score:2)
The address is hhelfgo at uni-math.gwdg dot de
Re: (Score:2)
Linking to that, when the (draft) paper goes up is much more appropriate than mucking around with emailing pre-prints.
Re: (Score:2)
You are right. I am so burning curious, however, to get a look at this stuff, that even the few days needed for arXiv to publish this, mean a win for me. (In my current project, a critical subsystem is a prime generator that might benefit from this).
Cube root (Score:1)
Re: (Score:1)
Re: (Score:3)
Yeah 2 seconds after I posted my second message I found myself wishing for an edit feature...
This is slashdot, we don't go for all those commie-pinko futuristic hand-holding features from the 1990's.
I mean, if we let people edit their posts (even just during a 1-minute grace period), ohmygod where will it end??
Re: (Score:1)
So, is it square root (100 is the square root of 10,000) or cube root (like the post said) or is it the square of the fifth root (100 compared to 100,000).
'cause so far the more information I'm given about this story the less I know, and the apology didn't actually clarify anything.
Re: (Score:2)
So, is it square root (100 is the square root of 10,000) or cube root (like the post said) or is it the square of the fifth root (100 compared to 100,000).
Yes.
Re: (Score:1)
Re: (Score:2)
Overhead would have to be ~78 sheets of paper. That doesn't seem right.
http://www.wolframalpha.com/in... [wolframalpha.com]
Re: Cube root (Score:2)
Which is all right since the cube root of 1e6 is 1e2. The previous best algorithm would require 1e4 pages.
Re: (Score:1)
Re: (Score:2)
Overhead would have to be 50 sheets of paper. doesn't seem right.
http://www.wolframalpha.com/in... [wolframalpha.com]
Re: (Score:3)
Where was this for my 1984 Science fair? (Score:4, Interesting)
Seriously. I got a scholarship using a TRS80 and the Sieve of Eratosthenes.
I'm no expert, but this seems useless. (Score:1)
A sieve gives you *all* primes, while encryption uses only specific primes. Pretty sure making a list of all primes of 4096 or less bits is one of those "more information than could be stored in the entire universe" things.
Re: (Score:2)
Re: (Score:2)
cbrt(2^4096)=1.014582607681846743926326542084877765671470485443624... × 10^411 bits
A terabyte is 2^40 bytes i.e. 2^43 bits. So yeah. Too much.
Re: (Score:2)
The news is about a cube root, not a square root.
Re: (Score:2)
The news is about a cube root, not a square root.
While you are right that the cube root is interesting, the Sieve of Eratosthenes is a different algorithm. Historically, you need an array of bits, with each bit set if it is the second bit after 2, the third bit after 3, the 5th bit after 5, etc. It is WAY faster than testing each number with the factors from 2 to the square root of the number.
As I understood it, rather than needing 1000 bits for the first 1000 numbers, you need cuberoot(1000) bits or 10 bits. They also say 1/5 the bits - so maybe someon
Re: (Score:3)
1000 bits, 168 of which are true (the 168 primes below 1000) and 832 are false.
Given this model of the data, the optimal encoding of the 1's should use 2.573 bits each, while the optimal encoding of the 0's should use 0.265 bits each.:
ln(1000/168) / ln(2) = 2.573... bits
ln(1000/832) / ln(2) = 0.265... bits
The space required for the entire sequence:
(168 * ln(1000/168) + 832 * ln(1000/832)) / ln(2) = 653.109... bits
The model would have to be significan
Anelloni (Score:5, Funny)
If I 3D-print a Sieve of Eratosthenes, can I use it to drain cooked pasta?
Re: (Score:3, Funny)
any pasta that is a multiple of another pasta's length will slip through. which would be the majority of the pasta. You're going to waste a lot of pasta doing this.
Re: (Score:1)
Re: (Score:3)
Um fellas .... (Score:1)
Re: (Score:2)
Re: (Score:3)
Adding 3 odd numbers gets you an odd number has never really astonished me.
Sure, but now we know that 206702934571364971352346820353 is guaranteed to have three prime addends.
And that ain't hay.
Re: (Score:2)
Re: (Score:2)
I really think an example like yours (except including the addends), or some other easier to see but valid example that adds to a prime like the first example would be more illustrative.
My example without the addends is sort of the point, right? I don't know what the addends are, but I am absolutely certain they exist. There's a proof. Pick any huge odd number you like, and the same guarantee exists. I'm not mathematician enough to guess how difficult it might be to find said addends, and digging around on Wolfram Alpha long enough to find out sounds too much like work for this time of night. But maybe it's difficult enough to be useful. And maybe not. Encryption is generally built
Re: (Score:1)
complexity (Score:2)
paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need (... about 100 sheets)
So it's O(sqrt(n)) space, what about time complexity? If it's O(n^2) thanks but no.
Re: (Score:2)
The abstract (in Spanish) (Score:1)
Moving window technique? (Score:2)
As part of a programming assignment I wrote two programs for finding primes.
The first one using a moving window technique. Lets say my window size is 100, so I fill in the numbers 1 to 100 into the window, do my sieve job on this, get the primes I got so far and put them in a list, and fill the window with the numbers 101 to 200, run them through the primes I got and then through whatever remains, extract the primes and add them to the list, etc...
The second was an instant filter system, i.e. I've got a lis
None of the above. (Score:4, Insightful)
"So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks?"
Neither.
It's a method to discover primes using elimination of non-primes up to the square root of the number you're after.
If you can get that far, you can get to the prime itself quite easily. It's not going to help discover new large primes without eliminating BILLIONS of numbers in between.
And from there it has nothing to do with cracking encryption whatsoever.
The impact of this is that a child's method of eliminating factorisable numbers slowly takes up slightly less storage space (i.e. slightly less variables held in RAM) than before. It's not a breakthrough in maths, but a slight efficiency saving in the computer science to perform the algorithm in practical terms.
References (Score:5, Informative)
Re: (Score:1)
Thank you Prof. Helfgott for speaking out.