Symbolic computing environments (sometimes invisibly) provide prime streams, i.e. bursts of consecutive primes. Note that it is possible to compute detached chunks of Eratosthenes's sieve near a trillion, say, from a dense sieve reaching only a million. I wonder if for this new sieve there's a visually satisfying cellular automaton analogous to Dean Hickerson's http://www.conwaylife.com/w/index.php?title=Primer (with video) or Adam Goucher's remarkable #C 10-state rule that supports a 2-cell prime number generator. #C It uses a similar principle to Dean Hickerson's "Primer" pattern, #C only 60 times faster. The sieves remove every multiple of #C each integer, except for that integer: #C Calcyman (Adam P. Goucher), 18 May 2009 x = 1, y = 3, rule = Primer H2$I! color=1 255 0 0 color=2 0 255 0 color=3 255 128 128 color=4 128 255 128 color=5 128 128 128 color=6 192 192 192 color=7 128 128 255 color=8 128 255 255 color=9 255 255 128 n_states:10 neighborhood:Moore symmetries:none #State 0: Empty Space #State 1: Up spaceship #State 2: Down spaceship #State 3: Up spaceship on reflector #State 4: Down spaceship on reflector #State 5: Reflector #State 6: Reflector in initial state #State 7: NW spaceship #State 8: E puffer #State 9: SE puffer var a={0,1,2,3,4,5,6,7,8,9} var b={0,1,2,3,4,5,6,7,8,9} var c={0,1,2,3,4,5,6,7,8,9} var d={0,1,2,3,4,5,6,7,8,9} var e={0,1,2,3,4,5,6,7,8,9} var f={0,1,2,3,4,5,6,7,8,9} var g={0,1,2,3,4,5,6,7,8,9} var h={0,1,2,3,4,5,6,7,8,9} var i={2,4} var j={1,3,6} var k={0,1,2,4,5,6,7,8,9} 0,i,a,b,c,d,e,f,g,2 5,i,a,b,c,d,e,f,g,3 0,a,b,c,d,j,e,f,g,1 5,a,b,c,d,j,e,f,g,4 0,a,b,k,7,c,d,e,f,7 0,9,a,b,c,d,e,f,g,7 8,a,b,c,d,e,f,g,h,5 9,a,b,c,d,e,f,g,h,6 0,9,a,b,c,d,e,f,g,7 0,a,b,c,d,e,f,8,g,8 0,a,b,c,d,e,f,g,9,9 1,a,b,c,d,e,f,g,h,0 2,a,b,c,d,e,f,g,h,0 7,a,b,c,d,e,f,g,h,0 3,a,b,c,d,e,f,g,h,5 4,a,b,c,d,e,f,g,h,5 6,a,b,c,d,e,f,g,h,5 (Pix near end of http://gosper.org/g12a.pdf (100M!).) --rwg On 2016-09-27 12:41, Andy Latto wrote:

On Tue, Sep 27, 2016 at 11:51 AM, Henry Baker <hbaker1@pipeline.com> wrote:

...

So what will be the impact of this?

I don't think it will have any practical or cryptographic effects, though it may lead to other faster algorithms that do, or other theoretically interesting algorithm improvements.

...

Will we see cheaper, lower-power encryption devices?

While many encryption algorithms start with "find a couple of large primes", I don't think this is a significant part of the running time of encryption algorithms. You can find candidates quickly by dividing by a few small divisors, then checking that 2^(p-1) = 1 mod p, and then only doing a full primality test for those that aren't ruled out by these two fast tests, which will have you doing at most a couple of full primality tests. Eratosthsenes' s sieve or improvements on it are good for finding all the primes in a range fast, but even with the improvements are slow compared to testing a single number for primality.

...

Or maybe quicker cracking times in brute force attacks?

As far as I know, attacks care about fast factoring, not fast primality testing or finding all of the primes in a range.

Andy.latto@pobox.com