Quadratic residue (mod p) using libnum
[Primes Home][Home]
If we have the form of \(x^2 = a \pmod p\), we must find a value of \(x\) which results in a value of \(a \pmod p\). It is actually a difficult problem to solve. If a solution exists, the value of \(a\) 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\)).
|
If we have the form of [1]:
\(x^2 = a \pmod p\)
we must find a value of \(x\) which results in a value of \(a \pmod p\). If a solution exists, the value of \(a\) is a quadratic residue (mod n). 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 example, if we have \(a=969\) and \(p=1223\), we get:
\(x^2 = 968 \pmod{1223}\)
For this we get a solution of:
\(453^2 = 968 \pmod{1223}\)
If we have \(a=1203\) and \(p=1223\), we get:
\(x^2 = 1203 \pmod{1223}\)
For this we get a solution of:
\(375^2 = 969 \pmod{1223}\)
Thus 968 and 1203 are quadratic residues modulo 1223.
The form of \(x^2 = a \pmod p\) is not always solvable:
For example, if we have \(a=209\) and \(p=1223\), we get:
\(x^2 = 209 \pmod{1223}\)
\(x^2 = 888 \pmod{1223}\)
Also, if \(a\) shares a factor with \(p\) it is also not solvable. For example:
\(x^2 = 39 \pmod{13}\)
will return a zero value for \(x\).
In this case we see that 10 is a possible quadratic residue for a \(p\) of 53. The solution is thus:
\({10}^2 = 47 \pmod{53}\)
import sys import random import libnum N=997 y=25 if (len(sys.argv)>1): y=int(sys.argv[1]) if (len(sys.argv)>2): N=int(sys.argv[2]) 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,{N: 1})): x=next(libnum.sqrtmod(y,{N: 1})) print (int(x)) print ("x=",x) print ("N=",N) print (" %d^2=%d (mod %d)" % (x,y,N)) else: print ("No Solution!!!!")
A sample run is:
y= 12 Find solution to x^2 = y (mod N) 5 x= 5 N= 13 5^2=12 (mod 13)