# 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:

It is these little bits of magic, that support methods such as RSA. The coding to prove these is here:

and the code is:

import randomfrom Crypto.Util.number import getPrime

from Crypto.Random import get_random_bytesimport sys

import sympyprimebits=16if (len(sys.argv)>1):

primebits=int(sys.argv[1])

if primebits>48: primebits=48while (True):

p_1 = getPrime(primebits, randfunc=get_random_bytes)

q_1= getPrime(primebits,

randfunc=get_random_bytes)

p=2*p_1+1

q=2*q_1+1

if (sympy.isprime(p) and sympy.isprime(q)): break;

g=3

x=random.randint(0,2**512)n=p*qres1=pow(g,x,n)res2=pow(g,x % (n),n)print (f"p={p}, q={q}, p'={p_1}, q'={q_1}, n={n}")print (f"\ng^x (mod n)={res1}\ng^(x (mod n)) (mod n) ={res2}")

if (res1==res2): print(" The same")

else: print(" Not the same")res2=pow(g,x % (p_1*q_1),n)print (f"\ng^x (mod n)={res1}\ng^(x (mod (p'q'))) (mod n) ={res2}")

if (res1==res2): print(" The same")

else: print(" Not the same")res2=pow(g,x % ((p-1)*(q-1)),n)print (f"\ng^x (mod n)={res1}\ng^(x (mod (p-1)(q-1))) (mod p) ={res2}")

if (res1==res2): print(" The same")

else: print(" Not the same")res1=pow(g,x,p)

res2=pow(g,x % (p-1),p)print (f"\ng^x (mod p)={res1}\ng^(x (mod p-1)) (mod p) ={res2}")

if (res1==res2): print(" The same")

else: print(" Not the same")

A sample run is:

p=116099, q=126839, p'=58049, q'=63419, n=14725881061g^x (mod n)=2833123105

g^(x (mod n)) (mod n) =10920218514

Not the sameg^x (mod n)=2833123105

g^(x (mod (p'q'))) (mod n) =2833123105

The sameg^x (mod n)=2833123105

g^(x (mod (p-1)(q-1))) (mod p) =2833123105

The sameg^x (mod p)=75307

g^(x (mod p-1)) (mod p) =75307

The same

And here is the code:

## Conclusions

It’s real shame that our kids know little of Leonhard Euler, or even of John Napier, but can tell you about Newton and Einstein. Both Euler and Napier have helped fixed the core flaws of the Internet, and continue to do so. If there is a Maths teacher at school who is struggling to show the relavent of logarithms in the class, there is no better example than the thing that saved the Internet: the Diffie Hellman key exchange method. Without that, the Internet could be one big spying network.

And did you known that Napier’s constant (2.718281828459) of *e* is named after Euler (‘E’uler’s constant)?

Go fall in love with numbers!