The prime numbers: from mystery to reality

in #mathematics8 years ago (edited)

Join me in my journey to decipher the mystery of the prime numbers.
I am fascinated by primes. I am into cryptography mainly because of them, and maybe, secret codes. Historically, they are the basis of modern cryptography and are most likely securing your https(the lock) connection to Steemit right now.

Through the mystery of the prime numbers

Prime numbers are among the few scientific "facts" that we most likely share with any, if they exist, alien species. No wonder, there were involved in the Arecibo message, the interstellar radio message being encoded in prime dimensions, 23×73.

Definition

Let's take the set of integers:
... , -100, -99, ... , -2, -1, 0, 1, 2, ... , 99, 100, ...

Divisor and Multiple

A number a is a divisor of a number b, if the remainder of the division of b by a is null
⇔ (is the same as) b = a × q for a certain number q
ba = q
b is a multiple of a

It follows that :

  • 0 has all the integers as divisors, except 0
  • 1 has only one divisor, itself

Optimus prime

A prime number is a number(positive integer) which has only two divisors: 1 and itself.
Let's look at some examples:
2 is prime because 1|2 ( | means "divides") and 2|2 and that's it. No other number divides 2.
3 is prime because 1|3 and 3|3 and that's it. No other number divides 3.
6 is not prime because 6 = 6×1 = 3×2, so its divisors are 1, 2, 3 and 6.
217 is not prime because 217 = 217 × 1 = 7 × 31

How do we find them

I will present you the historical way, the [sieve of Eratosthenes]( the sieve of Eratosthenes).

  • List all numbers from 1 to, say, 120.
  • Remove 1 since it is not prime
  • Circle the next number, which is 2, because it is not divided by anything not removed yet
  • Then remove all the multiples of 2
  • Jump to the next untouched number, which is 3
  • Then remove all its multiples (remember the rule of multiple of 3, don't you? 😋)
  • So on and so forth...
    You can see of it is done here (courtesy of wikipedia)

Why so important

Wikipedia:

For a long time, prime numbers were thought to have extremely limited application outside of pure mathematics.[12] This changed in the 1970s when the concepts of public-key cryptography were invented, in which prime numbers formed the basis of the first algorithms such as the RSA cryptosystem algorithm.

I will go into detail in the following posts, with subjects like quantum computing or elliptic curve, but let's be brief for now. Before the discovery of public cryptography, there was no way to exchange securely information with someone you didn't know, understand trust, first. Public cryptography is like having your mail box for anyone to send you a mail while only you have the key to open the box and see the mail. Online market would have never been possible without it.

Back to the maths for one last theorem. To understand the importance of prime number you have to understand this: if your house is number, your bricks are the prime numbers. They are the cells. Each number, that is stricltly higher than 1(>1), is a product of primes. Finding this decomposition is called Factorisation and this process plays a central role in the understanding and the security provided by the prime numbers. More on that later.

A number that is not prime is composite, as compose by a product of prime numbers, the numbers 0 and 1 not considered of course. This explains why on the sieve you have have the sieve of Eratosthenes. If instead of a table, you lay the number in a spiral, you get the very first picture of this post, which is called Ulam's spiral.

Next time we will dive slowly in the use of prime numbers in cryptography.
cryptography

Sort:  

I share you interest as well. It is my hope and fascination to someday learn the laws and order pulling the string behind this esoteric institute of pasterns. As much as its true that by figuring out this knowledge possess the treat of breaking crypto security, as we know it, due to yet to be innovations in factorizing large numbers. I also believe we have yet to discover a way to fortify through the re-imagination of a new form of crypto algorithm that still uses primes but is unbreakable by the art of factorizing large numbers. It may involve either a true one way function that not even trail and error can achieve,'OR' one that cuts close to that mark of expectation.

It's not often I stumble upon prime numbers fans like that :-)

Yes I was and am still fascinated by the prime numbers. That's how I got into cryptgraphy. It's a bid sad that it is not the direct base of the most used algorithm (elliptic curves, lattice,...). Maybe, as you say, we will find new ways to use them but we have to be aware of the Quantum computer threat.

Welcome on Steemit too.

Very interesting read. Thanks. Resteemed and followed.

thanks for steppin by and the comment.

This article is a must-read for any crunchers participating in various prime-searching distributed computing projects like PrimeGrid, GIMPS etc.

thanks @vortac. I knew I already spoke to you. It was with my other account (@jyezie) on this post. I think I was more motivated to write this post after yours. :-)

True Steemit synergy at work! Following both of your accounts.
BTW, SRBase project is also worth mentioning in this context, they are also looking for primes (and whitelisted by Gridcoin).

Thanks I will take a look at all of that. I am also looking forward to your next posts.

I love this post! Great stuff.

Coin Marketplace

STEEM 0.18
TRX 0.13
JST 0.029
BTC 58100.37
ETH 3135.49
USDT 1.00
SBD 2.24