Euler: One of The Fathers of Mathematics And Creators of a Foundation of Internet Security

For me, Leonhard Euler is one of the fathers of modern mathematics. He lived from 1707 to 1783, and had a stunning research career, including contributions to mechanics, music and fluid dynamics. His shadow thus looms large over our modern world, including within cryptography and in the security of the Internet.

One of his great theorems defined that:

aᴺ⁻¹≡1 (mod N)

The key factor here is that a and N should not share the same factors. We often define this as gcd(a,N)=1, and where gcd() is the greatest common denominator. If we use a few values of a and N we see [Try]:

>>> print 6**(6) % 7
1
>>> print 7**(10) % 11
1
>>> print 3**(16) % 17
1

We can also use two values for N, such as p and q, and where the power becomes (p-1)(q-1) [Try]:

>>> print 3**(16*10) % (17*11)
1
>>> print 5**(22*10) % (23*11)
1

Because of Euler’s Theory, we can state that:

In the following p, q, p′ and q′ are all prime numbers. If so we have the following truths:

The first of these is the foundation of RSA:

Let’s take a simple example of g=3, p=11, x=101: