Given a number ‘n’ and a prime ‘p’, find square root of n under modulo p if it exists. It may be given that p is in the form for 4*i + 3 (OR p % 4 = 3) where i is an integer. Examples of such primes are 7, 11, 19, 23, 31, … etc,
Input: n = 2, p = 7 Output: 3 or 4 3 and 4 both are square roots of 2 under modulo 7 because (3*3) % 7 = 2 and (4*4) % 7 = 2 Input: n = 2, p = 5 Output: Square root doesn't exist
Naive Solution : Try all numbers from 2 to p-1. And for every number x, check if x is square root of n under modulo p.
Square root is 3
Time Complexity of this solution is O(p)
Direct Method : If p is in the form of 3*i + 4, then there exist a Quick way of finding square root.
If n is in the form 4*i + 3 with i >= 1 (OR p % 4 = 3) And If Square root of n exists, then it must be ±n(p + 1)/4
Below is the implementation of above idea :
# An efficient python3 program to find square root
# under modulo p when p is 7, 11, 19, 23, 31, … etc.
# Utility function to do modular exponentiation.
# It returns (x^y) % p.
def power(x, y, p) :
res = 1 # Initialize result
x = x % p # Update x if it is more
# than or equal to p
while (y > 0):
# If y is odd, multiply x with result
if (y & 1):
res = (res * x) % p
# y must be even now
y = y >> 1 # y = y/2
x = (x * x) % p
# Returns true if square root of n under
# modulo p exists. Assumption: p is of the
# form 3*i + 4 where i >= 1
def squareRoot(n, p):
if (p % 4 != 3) :
print( “Invalid Input” )
# Try “+(n^((p + 1)/4))”
n = n % p
x = power(n, (p + 1) // 4, p)
if ((x * x) % p == n):
print( “Square root is “, x)
# Try “-(n ^ ((p + 1)/4))”
x = p – x
if ((x * x) % p == n):
print( “Square root is “, x )
# If none of the above two work, then
# square root doesn’t exist
print( “Square root doesn’t exist ” )
# Driver Code
p = 7
n = 2
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
Square root is 4
Time Complexity of this solution is O(Log p)
How does this work?
We have discussed Euler’s Criterion in the previous post.
As per Euler's criterion, if square root exists, then following condition is true n(p-1)/2 % p = 1 Multiplying both sides with n, we get n(p+1)/2 % p = n % p ------ (1) Let x be the modulo square root. We can write, (x * x) ≡ n mod p (x * x) ≡ n(p+1)/2 [Using (1) given above] (x * x) ≡ n(2i + 2) [Replacing n = 4*i + 3] x ≡ ±n(i + 1) [Taking Square root of both sides] x ≡ ±n(p + 1)/4 [Putting 4*i + 3 = p or i = (p-3)/4]
We will soon be discussing methods when p is not in above form.
This article is attributed to GeeksforGeeks.org