Intractable Problems in Public Key: SQUARING

Public key encrytion 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 (mod 32)

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 actually a…