Thank you to Adrien-Marie Legendre for his symbol

Okay. Let’s say you want to determine the square root of 16. Well, that’s easy … as the answer is 4. But now, what is the square root of this:

6131408466595397710012614540363234062359700887928125190599453844504986420213585686778819217466610878266563405415556

Ans: 2476168101441297080746512578325117519920374855425678540834L

In a world of public key cryptography, we often perform our operations within a finite field and use a prime number to define is finite field. Our operations are then undertaken with a (mod p) operation. Within elliptic curve methods we define the curve as:

y² = x³ + ax + b (mod p)

and where we have our (mod p) operations. But if we calculate a point x on this curve, how do we find out if we have an integer value squared and (mod p)?

If we have the form of y²=a (mod p), we must find a value of y which results in a value of a (mod p). It is actually a difficult problem to solve. If a solution exists, the value of a is a quadradic residue (mod p). In modular arithmetic this operation is equivalent to a square root of a number (and where x is the modular square root of a modulo p).

For this we turn to Adrien-Marie Legendre who, in 1798, defined the Legendre symbol. In the following we will try…