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 a modulo \(p\)). In the following we will try and solve for the value of \(x\). In this case we will create a modulus (\(N\)), and which is the product of two prime numbers (\(p\) and \(q\)):
Quadratic residue |
Outline
Let's say we select two large prime numbers (\(p\) and \(q\)), and then publish their product at \(N\):
\(N=pq\)
We now need to find a value \(y\), which satisfies this:
\(x^2=y \pmod N\)
For example, if \(y= 3\) and \(p=11, q=13\), then \(N=143\). Now we need to find the value of \(x\) for:
\({x}^2 = 3 \pmod{143}\)
The solution for this is \(x=126\):
\({126}^2 = 3 \pmod{143}\)
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]) if (len(sys.argv)>3): q=int(sys.argv[3]) N=p*q print ("p=",p) print ("q=",q) print ("y=",y) print ("\n\nFind solution to x^2 = y (mod N)") # Find solution to x^2 = y (mod N) if (libnum.has_sqrtmod(y,{p: 1,q:1})): x=next(libnum.sqrtmod(y,{p: 1,q:1})) print (int(x)) print ("x=",x) print ("N=",N) print (" %d^2=%d (mod %d)" % (x,y,N)) else: print ("No Solution!!!!") print ("\n\nFind solution to x^2 = y (mod p)") # Find 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!!!!") print ("\n\nFind solution to x^2 = y (mod q)") # Find solution to x^2 = y (mod q) if (libnum.has_sqrtmod(y,{q: 1})): x=next(libnum.sqrtmod(y,{q: 1})) print ("x=",x) print ("q=",q) print (" %d^2=%d (mod %d)" %(x,y,q)) else: print (")No Solution!!!!")
A sample run is:
p= 13 q= 11 y= 25 Find solution to x^2 = y (mod N) x= 5 N= 143 5^2=25 (mod 143) Find solution to x^2 = y (mod p) x= 8 N= 143 8^2=25 (mod 13) Find solution to x^2 = y (mod q) x= 5 N= 143 5^2=25 (mod 11)
And one without any solutions:
p= 59 q= 67 y= 31 Find solution to x^2 = y (mod N) No Solution!!!! Find solution to x^2 = y (mod p) No Solution!!!! Find solution to x^2 = y (mod q) No Solution!!!!