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\)). In the following we will try and solve for the value of \(x\), and also generate the Legendre symbol value [link]:
Quadratic residue (mod p) |
Theory
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\).
If we take a value of \(p=53\), we get the following values [here]:
0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
A sample run of the code gives:
Quadratic residue (mod n) solver a: 47 p: 53 We need to solve for: val^2 = 47 (mod 53 ) ----------------------- Result: 10 ( 10 )^2 = 47 (mod 53 ) ----------------------- For a prime number of 53 here are the residues up to p (or 100) 1 4 6 7 9 10 11 13 15 16 17 24 25 28 29 36 37 38 40 42 43 44 46 47 49 52
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}\)
Coding
The following is some example code [here]. It uses the Tonelli-Shanks algorithm [here] (as a prime number \(p\) is used:
# https://asecuritysite.com/encryption/modsq?Length=10 import sys def modular_sqrt(a, p): """ Find a quadratic residue (mod p) of 'a'. p must be an odd prime. Solve the congruence of the form: x^2 = a (mod p) And returns x. Note that p - x is also a root. 0 is returned is no square root exists for these a and p. The Tonelli-Shanks algorithm is used (except for some simple cases in which the solution is known from an identity). This algorithm runs in polynomial time (unless the generalized Riemann hypothesis is false). """ # Simple cases # if legendre_symbol(a, p) != 1: return 0 elif a == 0: return 0 elif p == 2: return p elif p % 4 == 3: return pow(a, (p + 1) // 4, p) # Partition p-1 to s * 2^e for an odd s (i.e. # reduce all the powers of 2 from p-1) # s = p - 1 e = 0 while s % 2 == 0: s /= 2 e += 1 # Find some 'n' with a legendre symbol n|p = -1. # Shouldn't take long. # n = 2 while legendre_symbol(n, p) != -1: n += 1 # Here be dragons! # Read the paper "Square roots from 1; 24, 51, # 10 to Dan Shanks" by Ezra Brown for more # information # # x is a guess of the square root that gets better # with each iteration. # b is the "fudge factor" - by how much we're off # with the guess. The invariant x^2 = ab (mod p) # is maintained throughout the loop. # g is used for successive powers of n to update # both a and b # r is the exponent - decreases with each update # x = pow(a, (s + 1) / 2, p) b = pow(a, s, p) g = pow(n, s, p) r = e while True: t = b m = 0 for m in range(r): if t == 1: break t = pow(t, 2, p) if m == 0: return x gs = pow(g, 2 ** (r - m - 1), p) g = (gs * gs) % p x = (x * gs) % p b = (b * g) % p r = m def legendre_symbol(a, p): """ Compute the Legendre symbol a|p using Euler's criterion. p is a prime, a is relatively prime to p (if p divides a, then a|p = 0) Returns 1 if a has a square root modulo p, -1 otherwise. """ ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else ls a=968 p=1223 rtn= legendre_symbol(a, p) print ("Quadratic residue (mod n) solver") print (" a:\t",a) print (" p:\t",p) print ("\nWe need to solve for:") print (" val^2 = ",a,"(mod ",p,")") print ("------") if (rtn==1): res=modular_sqrt(a, p) print ("Result:",res) print ("(",res,")^2 = ",a,"(mod ",p,")") elif (rtn==-1): print ("No value exists") else: print ("a shares a factor with p") print
The legendre_symbol returns:
- 1. When \(a\) is a quadratic residue of \(p\).
- -1. When \(a\) is a quadratic nonresidue of \(p\).
- 0. When \(a\) shares a factor of \(p\).
The notation used to define this operation is \( \left(\frac{a}{p}\right) \).
Tutorial
Prove these Legendre symbol values the following quanities \( \left(\frac{a}{p}\right) \):
- \( \left(\frac{15}{59}\right) = 1 \) Proof
- \( \left(\frac{44}{83}\right) = 1 \) Proof
- \( \left(\frac{12}{23}\right) = 1 \) Proof
- \( \left(\frac{11}{25}\right) = -1 \) Proof
- \( \left(\frac{2}{3}\right) = -1 \) Proof
- \( \left(\frac{2}{5}\right) = -1 \) Proof
- \( \left(\frac{2}{7}\right) = 1 \) Proof
- \( \left(\frac{1}{3}\right) = 1 \) Proof
References
[1] Hoffstein, Jeffrey, et al. An introduction to mathematical cryptography. Vol. 1. New York: springer, 2008.