Sweet are the uses of adversity

Sweet are the uses of adversity

Rock singers often say that it was their adversity that drove them to create their classics, such as heartache, sorrow, or losing something in their lives. And, so, we might quote:

Sweet are the uses of adversity — William Shakespeare

One such person who had considerable adversity is Leonhard Euler and who lived from 1707 to 1783. Leonhard was truly one of the greatest minds who has ever graced this planet:

“Read Euler, read Euler, he is the master of us all” — Pierre-Simon Laplace

But, he suffered great adversity in his life and eventually went blind. His blindness, though, seemed to just increase his outputs — as it allowed him to focus his mind on core problems. In fact, in 1775 — four years after he had gone blind — he proposed a mathematical paper every week. On going blind, he was quoted:

“Now I will have fewer distractions.”

Leonhard output of truly original thought in his time of adversity has possibly never been equalled by any mortal soul. And, his legacy lives on and is part of virtually every single transaction on the Internet. In fact, his maths has made our digital world so much safer.

The fundamentals

This article could in no way define all of Leonhard’s contributions, but one of the most fundamental is that he took the basics of integral calculus — as sketchily defined by Newton and Leibniz — and perfected it. In our modern world, so many things in our lives depend on calculus for their solutions, such as were we see changes in the physical parameters in our world. Calculus, for example, links the distances we travel over time to speed, and then changes in our speed to acceleration and deceleration. Overall, it basically makes sense of the dynamics of our world — an ever changing, and sometimes, chaotic world.

With Euler's identity, he showed that:

And where e is known as the Euler number — and is the base of natural logarithms, and where i is the square root of -1. This defines a complex number, and there are few things more beautiful in our world of mathematics than this formula. It is more generally defined as:

In electrical engineering, i is known as j (as i is often used to represent current in an electrical circuit). And so, we could express voltage as a vector, such as: 3+j4, and which has a magnitude of 5 and an angle of around 53 degrees. And so our sine waves could now be presented as a complex number, and opened up a whole new opportuity to fully understand the complex world of electrical circuits.

Proof of quadratic reciprocity

As someone who does cryptography, I spend a good deal of my time working with the most magical of all numbers: the prime number. And for many things that I do in public key encryption, I often end up using something that Euler created.

One of his greatest advancements related to the proof of quadratic reciprocity, which is used extensively in the area of elliptic curve cryptography. For this, we have x and N (and which is made of prime numbers) and need to find y which satisfies:

y=x² (mod N)

It was Euler who proved there were solutions to this. For example, if we

43=x² (mod 97)

The solution for this is x=72:

43= 72² (mod 97)

https://asecuritysite.com/principles_pub/modsq?aval=44&pval=83

Euler and public key encryption

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:

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 are here:

https://asecuritysite.com/principles_pub/euler01

and the code is:

# https://asecuritysite.com/encryption/modsq?Length=10
import sys

def modular_sqrt(a, p):
    """ Find a quadratic residue (mod p) of 'a'. p
        must be an odd prime.

        Solve the congruence of the form:
            x^2 = a (mod p)
        And returns x. Note that p - x is also a root.

        0 is returned is no square root exists for
        these a and p.

        The Tonelli-Shanks algorithm is used (except
        for some simple cases in which the solution
        is known from an identity). This algorithm
        runs in polynomial time (unless the
        generalized Riemann hypothesis is false).
    """
    # Simple cases
    #
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)

    # Partition p-1 to s * 2^e for an odd s (i.e.
    # reduce all the powers of 2 from p-1)
    #
    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1

    # Find some 'n' with a legendre symbol n|p = -1.
    # Shouldn't take long.
    #
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1

    # Here be dragons!
    # Read the paper "Square roots from 1; 24, 51,
    # 10 to Dan Shanks" by Ezra Brown for more
    # information
    #

    # x is a guess of the square root that gets better
    # with each iteration.
    # b is the "fudge factor" - by how much we're off
    # with the guess. The invariant x^2 = ab (mod p)
    # is maintained throughout the loop.
    # g is used for successive powers of n to update
    # both a and b
    # r is the exponent - decreases with each update
    #
    x = pow(a, (s + 1) / 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


def legendre_symbol(a, p):
    """ Compute the Legendre symbol a|p using
        Euler's criterion. p is a prime, a is
        relatively prime to p (if p divides
        a, then a|p = 0)

        Returns 1 if a has a square root modulo
        p, -1 otherwise.
    """
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

a=968
p=1223


rtn= legendre_symbol(a, p)

print ("Quadratic residue (mod n) solver")
print (" a:\t",a)
print (" p:\t",p)
print ("\nWe need to solve for:")
print ("  val^2 = ",a,"(mod ",p,")")
print ("------")
if (rtn==1):
 res=modular_sqrt(a, p)
 print ("Result:",res)
 print ("(",res,")^2 = ",a,"(mod ",p,")")
elif (rtn==-1):
 print ("No value exists")
else:
 print ("a shares a factor with p")
print 

A sample run is:

Quadratic residue (mod n) solver
 a: 47
 p: 53

We need to solve for:
  val^2 =  47 (mod  53 )
-----------------------
Result: 10
( 10 )^2 =  47 (mod  53 )

-----------------------
For a prime number of  53 here are the residues up to p (or 100)
1 4 6 7 9 10 11 13 15 16 17 24 25 28 29 36 37 38 40 42 43 44 46 47 49 52

Conclusions

It’s a 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.

And, so, when you are faced with adversity, think of Euler, and overcome it.

References

Shakespeare, William. The complete works of William Shakespeare. Race Point Publishing, 2014.