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.

Prime Number Generator: Chapter 2 - the Validation

It is a peculiar taste one acquires as the currents of time write the truth on the walls of experience.

How can one truly understand the realities that exists beneath the colors one projects onto the 3-dimensional landscape of desire, hope and belief? 

Chapter 2 - the Validation

Was I moving towards truth as I walked to my meeting with Dr. Atkinson – filled with excitement mixed in with some “trepidation”? 
Was it “realistic” to believe that there was actually $100,000 available for the taking? In hind sight, it seems rather silly and trivial that I happened upon Eratosthenes' sieve, expressing patterns with summations and basic boundary conditions. 

Interesting connections that flair our taste buds – sweet and sour, salty and sweet, bitter and sweet, excited and nervous, prime numbers and monetary rewards, encryption and CORA. 

I put one foot in front of the other and walked head on into the lion’s lair, to meet Dr. Atkinson. He was truly kind and disarming; very approachable and down to earth. 
A bashful 18-year-old with a strange mix of certitude and confidence, that was fueled by thoughts of $100,000, sat with Dr. Atkinson whose smile was warm and comforting. 

I was summoned to the University to speak with Dr. Barry Fawcett. I was left with some papers that were correspondences between Dr. Fawcett and Dr. Atkinson.

page 1 of 3

 What happened during this meeting you ask? What did Dr. Fawcett say?

1. My prime number generator did generate the entire set of prime numbers. 
2. It was similar to Eratosthenes’ sieve but did have some merit as it simplified the calculations. (see Chapter 3 for a surprising discovery about "organic-sieves")
3. There was no reward. (sad face - the $100,000 was noteworthy as an incentive, but fell short as a reward)
4. There were two other prime number generators developed my mathematicians, one group in Russia, and another out West.
5. He suggested that mine had some merit as it involved fewer variables
   (3 rather than 10).

Dr Fawcett suggested that I should write an article in a Mathematical Journal. Sadly, I had no idea what that would involve, or what significance an article to a journal would have.
I had never even seen such a journal, or article. Moreover, in an instant, I had lost $100,000 – or so it felt.

Redemption 

Dr. Fawcett went on to explain why prime numbers are important. 

Encryption uses prime numbers as the keys that lock and unlock data. If two very large prime numbers are (simplified version) multiplied together, they will produce an even larger number. This composite number would have only two divisors that leave no remainder.

I left his office, papers in hand, and a wallet that felt very light indeed. I tucked away the memory of encryption and prime numbers until it would resurfaced again, many years later. 

Timing

This was many years before “the internet”, and many years before the notion of a “home computer” – we were still using “punch cards” to enter instructions into a computer.

I blinked

I was no longer programming in Fortran 77. I hadn’t seen a punch card for decades. I was typing my instructions directly into a computer as I watched these programs execute in real time - on my monitor - WOW. 

I loved the freedom and complexities that programs like C brought to the playing field. I reveled in the convenience of IDE’s like Borland C, then C++. 

Modems appeared on the scene and suddenly I began to cave in and use passwords on my computer. The Internet appeared – such a brave new world.

Then one day I encrypted a technology base I was working on and decided to upload it to "the Internet" for safe storage, and I remembered – encryption – and the keys – prime numbers. 

Yes, if anyone really wanted to unlock my technology, they could simply try all the large primes until they found “my keys”. If they too had a prime number generator, then the time required to find those keys would be greatly reduced. I realized that encryption was not protecting my data from everyone, but rather, only from those who would never acquire it in the first place.

Still to come

Chapter 3 - the Generator (will be posted this Thursday, 19 May 2016)

Prime Number Generator: Chapter 1 - the Challenge

My next few posts will constitute a “sub series” about my Prime Number Generator. This series is related to a far broader and more important series on “Encryption – breaking the myth”.
In the last two posts, I have endeavored to present empirical data. Pragmatically one may easily recognize that:
1. Encryption is being used to secure data.
2. Breaches have occurred.
3. Readable data was acquired by those who don’t have a right to the data.
4. Conclusion: Encryption is failing to properly secure data.

Chapter 1 – the Challenge

The year is 1977. Location: Windsor Ontario, Canada. Yes, once upon a time, Ontario had 5 years of high school. Juniors are in grades 9 and 10. Seniors are grouped into grades 11, 12 & 13.

Happily, there were three math courses offered in Grade 13, and this lover of math signed up for all three.

Mr. Taylor taught Algebra. He was introducing “Prime numbers”. Optimistically he endeavored to engage his students by announcing a $100,000 reward for anyone that developed a prime number generator - for the entire set.

I would like to think I was motivated by “the challenge”, however, truth be said, it was the money. I became excited. Didn’t much care for the homework, but I couldn’t wait to get home to work on it. I found my way to the dining room table, and delved into the possibilities. Numbers scattered across reams of paper, patterns everywhere – but which pattern might be “the one”?

Math is beautiful – I was enjoying the challenge, the possibilities, the patterns. When all is said and done, math and science is basically about patterns that can be interpreted and reproduced.

After a few weeks, and more paper than I had ever used for “home work”, I had distilled the patterns down to one, that worked for all prime numbers except for the lonely, even numbered - prime number of “2”. 

If I had understood back then “why” prime numbers were important, I wouldn’t have wasted another moment on “the technicality” of included “2” in the output produced by my prime number generator. Perhaps I thought like a lawyer, or a strategist, but I couldn’t take a chance that, omitting “2”, might ruin my chance of winning the reward.

I approached Mr. Taylor at school during lunch. As a prelude to my bottom line, I advised him that I had the prime number generator, then asked how I go about claiming the $100,000. 
At first he smirked as though I was pulling his leg with a sarcastic prank, then as he realized that I “wanted the money”, he arranged for me to see Dr. Harold Atkinson, the head of the math department at the University of Windsor.


Fellow classmates C. Collins and D. Girard translated this Prime Number generator into “WATFIV”, using those good ole punch cards and a large main frame computer. The printout included a large number of prime numbers as an early, pragmatically driven test of this prime number generator. These printouts along with the mathematical representation of the generator were brought to Dr. Atkinson.

Still to come:

Chapter 2 - the Validation (Tuesday, 17 May 2016)
Chapter 3 - the Generator (Thursday, 19 May 2016)