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
⇔ ^b⁄_a = 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