Prime Number Generator: Chapter 3 - the Generator

The Generator

Here is the original statement of my Prime Number Generator. There is a Formula followed by restrictions:

Formula

The  n Î N_o  is unnecessary – including the first prime, the even prime, “2” is irrelevant in the scope of its application to encryption. As a utilitarian methodology, it is not needed (see the revised expression below).

Restriction

Let's revisit this expression and simplify it

If we omit "2", then this equation is much simpler: 

Formula

          P = 2n+1

Restriction

n ¹ 4R(R+1)/2 + (2R+1)m

or, expressed differently

n ¹ 2R²+2R(m+1) + m

For demonstration purposes only, an old JavaScript based version is available at http://CORAcsi.com/PrimeNumbers

So where's the fun in an older, slower, sieve based Prime Number Generator?

When teaching Math and Physics I start class with a quote and some tidbits. One such tidbit involves Mersenne Primes. I became aware of the Great Internet Mersenne Prime Search at www.Mersenne.org. For years they offered a $250,000 reward for the first person that found a 1 billion digit Mersenne Prime.

Oh yes, I verified this challenge!

I encouraged my students to pursue this, offering them my Prime Number Generator, and my assistance with the technologies involved. A number of groups embraced the challenge, however, they did not persevere. Then some number of years ago, the URL's by which I had verified this reward had disappeared. I couldn’t verify the $250,000 reward, and I certainly didn't want to mention a reward that "might not be available".

One of the drawbacks to a sieve approach is the amount of memory needed to continue the pattern. Essentially it is necessary to remember the past. This is considered a drawback, and certainly it would be for a normal sieve.

It's like making a snow man, the more your roll the snowball, in the snow, the larger it becomes.

Time to play

A few years ago I decided to play with my original generator. During that time I became aware of an interesting pattern that emerges if one gets creative with the binary sequences that would generate a very large prime. Essentially it would be possible to generate an “organic sieve” that could be used to perpetuate this continued pattern. Run the organic sieve for a few hours today, then again in a week for a few more hours. Every time it is run, it grows - and can then be used to reveal more prime numbers.

An organic sieve could be called "Frosty the snow man". It grows just like cited above. The difference being, that the molecules of frozen water in "Frosty", each can point to a prime number.

The existing “prime numbers” are essentially the generators (or eliminators in the sequence) of the, yet to be generated primes. If one were to creatively design a data structure to hold “the generated primes” in such a way that this “organic sieve” not only represents a “projector to known primes”, but a generator of “yet to be known” primes, then it becomes a growing entity that can be static in use, or dynamic in the generation of more primes. 

In other words, this organic sieve in its static state is like a write once, read many times, lookup table. Use it today to quickly look up any “known prime”. If in a few years, one wants more “immensely large primes”, then run the organic sieve dynamically for a few days, and it will grow, producing an even larger “static form” that can be used to look up more “immensely large primes”.

How big, is big?

Consider for a moment that a 1 billion digit Mersenne prime would require just about half a GB (more than 415 billion bytes) just to store. This means that half a GB of RAM would be used to simply hold this enormous Mersenne Prime. A similar amount of space would be needed to store it – a single prime number.

The one drawback if you will, is the size of this “organic sieve”. An organic sieve that represents all prime numbers up to and including this 1-billion-digit prime would require approx. 780 trillion bytes. 

Altruistic anyone?

I didn’t bother to finish this organic sieve. It wasn't sufficiently interesting beyond the concept stage, nor was it important enough in comparison to CORA. I mention it here because, you surely know that there are so many incredibly smart people in this world. I am confident that others have already done this. 

Bottom line – primes are obtainable in an efficient manner. Hence, Encryption isn’t a safe manner to protect data – static data. Encryption may be fine for communication – data in transit – however, as should be obvious with the number of reported breaches and loss of data and money – encryption is breakable!

Memory lane

I have shared this little trip down memory lane with you, in the hope that you will more fully realize “why encryption doesn’t cut it any more”. As our computers become more powerful, and can generate larger prime numbers, they are also more powerful in the finding of these prime numbers, particularly if one is using a prime number generator, or an organic sieve.

This was my motivation to develop CORA! 

Should there be any fellow math enthusiasts and/or technology lovers out there that would like to delve into this generator or organic sieve, enjoy, and let me know how it goes.