If we have the form of \(x^2 = y \pmod p\), we must find a value of \(x\) which results in a value of \(y \pmod p\). It is actually a difficult problem to solve. If a solution exists, the value of \(y\) is a quadratic 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 \(y\) modulo \(p\)).
Quadratic residue \(\pmod p\) |
Outline
Let's say we select a prime number of (\(p\) and \(q\)). We now need to find a value \(y\), which satisfies this:
\(x^2=y \pmod p\)
For example, if \(y= 3\) and \(p=659\). Now we need to find the value of \(x\) for:
\({x}^2 = 3 \pmod{659}\)
The solution for this is \(x=176\):
\({176}^2 = 3 \pmod{659}\)
Coding
The coding is here:
# https://asecuritysite.com/encryption/q_res?Length=10 import sys import random import libnum p=11 q=13 y=25 if (len(sys.argv)>1): y=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) print ("p=",p) print ("y=",y) print ("\n\nFind solution to x^2 = y (mod p)") if (libnum.has_sqrtmod(y,{p: 1})): x=next(libnum.sqrtmod(y,{p: 1})) print ("x=",x) print ("p=",p) print (" %d^2=%d (mod %d)" % (x,y,p)) else: print ("No Solution!!!!")
A sample run is:
p= 659 y= 3 Find solution to x^2 = y (mod p) x= 176 p= 659 176^2=3 (mod 659)
and where there is no solution:
p= 11 y= 101 Find solution to x^2 = y (mod p) No Solution!!!!
This type of approach is used in elliptic curve cryptography (ECC) and where we have the form of:
\(y^2 = x^3 + ax +b \pmod p\)
If we have an \(x\), we then need to find the quadratic residue of \(x^3 + ax +b \pmod p\), in order to find the \((x,y)\) point. For example, if we use \(p=13\), \(a=0\) and \(b=7\), for \(x=5\), we get:
\(y^2 = 5^3 + 7 \pmod {13} = 132 \pmod {13}\)
There is no solution to this, and thus a point does not exist at \(x=5\). If we try \(x=6\), there will also be no solution. But if we now try \(x=7\)
\(y^2 = 7^3 + 7 \pmod {13} = 350 \pmod {13}\)
We get a solution of \(y=8\), and this have a point at \((7,8\)):
p= 13 y= 350 Find solution to x^2 = y (mod p) x= 8 p= 13 8^2=350 (mod 13)