Quadratic Roots for a Modulo of a Prime of 5 (mod 8)

Public key encryption has a range of number theoretic problems, of which there is no actual proof of security [1]:

These are intractable at the current time with the right parameters. For example, RSA depends on FACTORING and RSAP. With this, if we have C= M^e (mod N), then it is difficult to determine M, even if we know C, e and N (RSAP). Also, since the modulus (N) is made up of two prime numbers (N=p.q), we also have FACTORING.

One of the number theoretic problems is SQROOT, we have the form of:

x²=a (mod N)

a is then the square root of a modulo N. For example, if N=32, we can have:

18²=4 (mod32)

Thus the square root of 18 modulo 32 is 4 — and which is known as the quadratic residue.

Overall, it is a hard problem to compute if N is a composite number, but can be computed efficiently if it is a prime number.

Square root modulo with a prime number

If we have the form of x²=a (mod p), we must find a value of x which results in a value of a (mod p). It is…