by March 28, 2020
I used to work in a restaurant with my best friend. They had prime rib night once a week. My friend used to call it rib that was divisible by one or itself. Ba-dum-baaaaa!
Until the past couple of years, I was never very interested by prime numbers; Never enough to bother trying to learn why I should be fascinated by them. As we all learned in high school, a prime number is any natural number greater than one which can only be divided by one or itself, without a remainder. That’s about as far as my high school got with primes.
Turns out they are incredibly useful in computing and cryptography, yet there is still no really efficient method to find them and the larger the prime number the longer it takes to find the next one.
The largest prime number I know is Jenny’s… 8675309.
The Greek scholar of the third century BC, Eratosthenes proposed a simplified algorithm for finding prime numbers up to a given limit, known as the Sieve of Eratosthenes.
To test if a number (x) is prime, we can check if it’s divisible by all primes less than or equal to the square root of x. If x is not a prime number, then it can’t have a factor bigger than its square root. That shortens the list for proving primality a lot and could be useful for smaller numbers, but for the much larger numbers needed in computing and cryptography this method still requires us to do extensive calculations to find primes.
Although still requiring intensive computation, newer algorithms have improved on this and though there are an infinite number of primes, they become less frequent as you try to find them counting up toward infinity. This is why finding new primes is so valuable.
As of January 2017, the largest known prime number is 274,207,281 – 1, a number with 22,338,618 digits. There are prizes offered by the Electronic Frontier Foundation for primes of 100 million digits and larger with USD $150,000 – $250,000 prize for winning participant(s). The Great Internet Mersenne Prime Search is looking for a special prime number called a Mersenne prime — a prime number where the exponent is also a prime.
Ok, now they’re just trying to make my head hurt.
One of the properties that make primes so valuable in computer security, secure online transactions, and cryptography is that while it is possible to calculate large prime numbers, it’s incredibly hard to factor large numbers back into primes.
Modern computer cryptography takes advantage of this principle by using the prime factors of very large numbers. The large number that was used to encrypt a file, usually called the public key, can be publicly known and distributed freely to whomever because the decryption can only be accomplished using the prime factors of that large number (the private keys). Finding those factors can be done but is only a matter of time… a lot of time… so much time that our sun will die and Earth will be uninhabitable before it will be cracked.
Cryptography is not about being un-crackable but more about being such a huge roadblock to get around that it becomes unfeasible to reasonably do so. A 256 bit decryption problem could take longer than the age of the universe to decrypt, even using the fastest supercomputers we have.
Forget what you see on TV and in Movies… Hackers don’t break strong encryption. Hackers have been taking advantage of flaws in security software or more commonly bad security practices by computer users and social engineering exploits.
While it remains to be seen if quantum computing will be a game changer of any kind in the future of cryptography (probably), this method of storing our secrets and locking up our electronic valuables currently remains the most secure. The thing you should do besides having a strong encryption scheme is to educate yourself on best security practices to prevent the more common ways hackers get into your accounts; Weak passwords, systems that aren’t updated, and the lack of 2 factor authentication are all ways that you can be more vulnerable to hackers,
My math teacher in high school never told me prime numbers could be so cool!
— CSH [not a mathematician]
Related video… It’s about CSS DVD encryption but does explain encryption concepts pretty well:
