Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Math Software News Science Technology

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.
This discussion has been archived. No new comments can be posted.

Researcher Modifies Sieve of Eratosthenes To Work With Less Physical Memory Space

Comments Filter:
  • by UnknownSoldier ( 67820 ) on Monday September 26, 2016 @07:38PM (#52966265)

    *sigh*

    Getting tired of "news" posting _zero_ details.

    Does anyone have details on the actual algorithm? Reference Implementation?

    • by seoras ( 147590 )

      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?

    • by Roger W Moore ( 538166 ) on Monday September 26, 2016 @08:39PM (#52966577) Journal

      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.

    • 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.

    • 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.

      • 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.)

      • With 43 papers on Arxiv answering to that author surname, I suspect that the paper will be there some day. (That search's most recent result was "1. arXiv:1512.02135 Soficity, short cycles and the Higman group " ; other papers in the results relate to work on primes, so it looks as if this is the correct author.)

        Linking to that, when the (draft) paper goes up is much more appropriate than mucking around with emailing pre-prints.

        • 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).

  • Since when is the cube root of 10,000 equal to 100? That's a much more interesting discovery!
    • Which is all right since the cube root of 1e6 is 1e2. The previous best algorithm would require 1e4 pages.

  • by burhop ( 2883223 ) on Monday September 26, 2016 @07:54PM (#52966347)

    Seriously. I got a scholarship using a TRS80 and the Sieve of Eratosthenes.

  • by Anonymous Coward

    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.

    • cbrt(2^4096)=1.014582607681846743926326542084877765671470485443624... × 10^411 bits

      A terabyte is 2^40 bytes i.e. 2^43 bits. So yeah. Too much.

  • Anelloni (Score:5, Funny)

    by PopeRatzo ( 965947 ) on Monday September 26, 2016 @08:18PM (#52966481) Journal

    If I 3D-print a Sieve of Eratosthenes, can I use it to drain cooked pasta?

    • Re: (Score:3, Funny)

      by Anonymous Coward

      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.

    • by Anonymous Coward
      You're thinking of a Colander of Eratosthenes. You're obviously not a Pastafarian.
    • Not really - since the distance between prime numbers gets big quite quickly, your sieve would quickly almost not have any holes at a certain point.
  • "Goldbach’s weak conjecture, according to which every odd number greater than 5 can be expressed as the sum of three prime numbers—such as: 3 + 3 + 5 = 11 and 19 + 13 + 3 = 35." Hmmmm.
  • 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.

  • 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)

    by ledow ( 319597 ) on Tuesday September 27, 2016 @03:29AM (#52967933) Homepage

    "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)

    by HHelf ( 4723751 ) on Tuesday September 27, 2016 @07:59AM (#52968603)
    I was about to post something longer, but my computer deleted it at just the right moment. Summary: (a) The origin of this article was an interview given at an algebra colloquium in Buenos Aires a few weeks ago. Its appearance in Scientific American was a little unexpected (to me). I should be able to post a preprint soon. (b) In my colloquium talk, I made sure to mention that I had just come across a precedent in the literature: W. F. Galway, Dissecting a sieve to cut its need for space. In Algorithmic number theory (Leiden, 2000), vol 1838 of Lecture Notes in Comput. Sci., pages 297-312. Springer, Berlin, 2000. In both cases, we are talking about space essentially O(N^(1/3)) and time essentially O(N). Galway improves on the Atkin-Bernstein sieve, which is specifically about producing lists of primes. The sieve of Eratosthenes can be used for more general purposes, e.g., producing lists of factorizations or computing tables of values of arithmetic functions that depend on factorization. I actually got interested in the problem while using a sieve to produce successive values of mu(n), where mu is the Moebius function. As far as I can tell, there's a basic underlying idea being used in both cases, viz. Diophantine approximation. In brief, if you are finding primes (or what have you) in an interval [N,N+N^(1/3)], you do not have to sieve by every m=sqrt(N); you can tell in advance which integers m will have no multiples in that interval. This is all more or less orthogonal to [http://sweet.ua.pt/tos/software/prime_sieve.html]. Indeed what I do and what Oliveira e Silva does can very likely be combined. Best Harald Helfgott
    • by Anonymous Coward

      Thank you Prof. Helfgott for speaking out.

Adding manpower to a late software project makes it later. -- F. Brooks, "The Mythical Man-Month"

Working...