Prime numbers and the importance to modern life

So you’ve graduated high-school, or even made it through university. If you’re reading this article we expect you to understand at least the basics about Prime Numbers. Primes are the set of all numbers that can only be equally divided by 1 and themselves, with no other even division possible.

Numbers like 2, 3, 5, 7, and 11 are prime numbers, but what few people realize is the importance of these numbers and how the mathematical logic behind them has resulted in vital applications in modern world.

Let’s see something cool about primes: Mathematicians have shown that absolutely any whole number can be expressed as a product of primes, only primes, and nothing else. For example:

To get 222, try 2 * 3 * 37

36,230,980? Why, that’s just, 2 * 2 * 5 * 23 * 79 * 997

Or look at the tree of how the above primes are made up:

 36230980     
 /  \     
2 18115490    
  /  \    
 2 9057745   
   /  \   
  5 1811549  
    /  \  
   23 78763 
     /  \ 
    79 997


Sometimes of course you might find the calculation instead of 2 * 2 * 5 * 23 * 79 * 997 look like this: 22 x 51 x 231 x 791 x 9971, which is just the exponential form of writing the same arithmetic process.

So now do some simple calculations on your own to get a feeling. For your convenience we’ve attached a Prime Numbers Table till 1000.

Table of Prime Numbers until 1000
Table of Prime Numbers until 1000

This fundamental rule is called the “prime factorization rule” or in the more scientific terminology the “Fundamental Theorem of Arithmetic” [1].

Primes are numbers that can’t be pulled apart any further. So as we try to pull apart any number into two numbers, then pull those apart into two numbers if possible, and so on, we will eventually be left only with Prime Numbers.

Some might argue that this is nothing more than a mathematical oddity. But there is another fact that adds importance: Mathematicians and computer scientists have determined that it is impossible to establish an efficient formula for factoring large numbers into primes.

That being said, there are ways of factoring large numbers into primes, but if we try to do it with a 200-digit number, or an even bigger 500-digit number, applying the same algorithms, we would use to factor a 7-digit number, the world’s most advanced supercomputers [2] would take an absurd amount of time to finish calculating the building blocks of the number – or the Primes. Just to give you an idea of the scale: Factoring a 500 digit number into its primes could take as long as the formation of the planet and for extremely large numbers, the factoring process could take longer than the age of the universe itself.

As we are able to establish, the functional limit to the size of the numbers we are able to factor into primes is limited. This fact however, is vital to modern computer security. Now, looking at the above problem from the perspective of computer security, we understand that there is a great interest to solve the problem, and being able to factor large number into primes in reasonable time.
Most current encryption algorithms exploit the fact that we can easily take two large primes and multiply them together to get a new, super-large number, but at the moment no computer yet created can take that super-large number and quickly reverse it into the two primes which make it.

This simple mathematical security is the base for the so called public key cryptography [3], or in other words, an encryption technique in which we do not require to worry about the public key part of the key. This Public Key can be openly distributed (and is required to be distributed) to any third party that wishes to decrypt the contents whatever is encrypted with the key in question.

Knowing the public key to encrypted information won’t help anyone to decrypt the encryption it created. In order to decrypt, and read the file or message, a vital part is knowing the prime factors of the key used for encryption — and just as we explained above, this is not something you can just “figure out” on your own.

So how do you securely communicate the initial specifics needed to set up secure communication in the first place?

In public key cryptography, which is the backbone of computer encryption, we can get around this because the specifics of how to get into secure contact don’t themselves need to be secure.
As a matter of fact, exactly the opposite is the case - people generally post links to their public keys on social media, so as many people as possible will be able to encrypt messages for them. Though there are now quite a few encryption algorithms that exploit prime factorization, the most historically significant, and still the conceptual blueprint for the field, is called RSA [4].

We are using computer encryption all the time e.g. when communicating our credit card information to an online merchant, logging into our bank, or sending a manually encrypted email to a colleague. Summarizing this means that we are relying on prime numbers throughout all our virtual life – day in, day out.

To understand prime numbers is no senseless quest, nor a purely scientific challenge, but rather the greater understanding of the limitations all our security relies on. Especially if one takes into account that there has been no progress in factoring large numbers for several years now. 

Researchers have networked several hundred computers together and spent the equivalent of several thousands of years for a single computer, using advanced factoring algorithms to factor the “RSA-768″ number — that is to say, a number with 232 digits put up by the RSA group as a factoring challenge.

Proving it was possible to break 768-bit encryption in non-universal-heat-death timescales is unacceptable for the world of security experts, and thus as a reaction the standard for modern encryption moved on to RSA-1024, using numbers with 309 digits and RSA-2048 with 617 decimal digits.

1024- and 2048 bit encryptions are supposed to be safe from anyone not in possession of a time machine, as far as we know — however lately novels like Digital Fortress by Dan Brown [5] and Contact by Carl Segan [6] refer to a secret NSA project, which supposing is in the possession of secret Quantum Computer Technology [7] which can chew through even 2048-bit encryption in reasonable time.

Quantum Computing is lately heavily in the press and Google together with NASA work on a project to make Quantum Computing the standard, however there is absolutely no evidence that quantum computing can break numbers based on 1024 or 2048 bit encryption.

There is a certain importance to prime number factorization as being the fundamental building blocks of all numbers, which are themselves the root for understanding the universe [8].

Some mathematicians describe number theory a little bit like archaeology. The feeling isn’t one of inventing new technologies, but of uncovering the logical foundations of the universe, those that describe its behaviour everywhere, throughout all of time.

The CodeCoda Research Lab, inspired by “Digital Fortress” works on a concept for a new Encryption Algorithm that makes it impossible to break by factoring numbers – Therefore the “Fundamental Theorem of Arithmetic” is one of the building blocks of such an algorithm and the detailed understanding of Prime Numbers is vital to building the next generation of quantum safe encryption.

References

  1. Fundamental Theorem of Arithmetic
  2. Supercomputers
  3. RSA Description Wikipedia
  4. Public-key cryptography Wikipedia
  5. Digital Fortress, Dan Brown, 1998
  6. Contact, Carl Segan, 1985
  7. The bits, the bytes and the quants, Andreas Maier
  8. Why Math is the language of the Universe, Team Futurism, 2013