# Find Square Root under Modulo p | Set 1 (When p is in form of 4*i + 3)

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,

Examples:

```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.

## C++

 `// A Simple C++ program to find square root under modulo p ` `// when p is 7, 11, 19, 23, 31, ... etc, ` `#include ` `using` `namespace` `std; ` ` `  `// Returns true if square root of n under modulo p exists ` `void` `squareRoot(``int` `n, ``int` `p) ` `{ ` `    ``n = n % p; ` ` `  `    ``// One by one check all numbers from 2 to p-1 ` `    ``for` `(``int` `x = 2; x < p; x++) { ` `        ``if` `((x * x) % p == n) { ` `            ``cout << ``"Square root is "` `<< x; ` `            ``return``; ` `        ``} ` `    ``} ` `    ``cout << ``"Square root doesn't exist"``; ` `} ` ` `  `// Driver program to test ` `int` `main() ` `{ ` `    ``int` `p = 7; ` `    ``int` `n = 2; ` `    ``squareRoot(n, p); ` `    ``return` `0; ` `} `

## Java

 `// A Simple Java program to find square ` `// root under modulo p when p is 7,  ` `// 11, 19, 23, 31, ... etc, ` `import` `java .io.*; ` ` `  `class` `GFG { ` ` `  `    ``// Returns true if square root of n ` `    ``// under modulo p exists ` `    ``static` `void` `squareRoot(``int` `n, ``int` `p) ` `    ``{ ` `        ``n = n % p; ` `     `  `        ``// One by one check all numbers ` `        ``// from 2 to p-1 ` `        ``for` `(``int` `x = ``2``; x < p; x++) { ` `            ``if` `((x * x) % p == n) { ` `                ``System.out.println(``"Square "` `                    ``+ ``"root is "` `+ x); ` `                ``return``; ` `            ``} ` `        ``} ` `        ``System.out.println(``"Square root "` `                ``+ ``"doesn't exist"``); ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `p = ``7``; ` `        ``int` `n = ``2``; ` `        ``squareRoot(n, p); ` `    ``}  ` `} ` ` `  `// This code is contributed by Anuj_67 `

## Python3

 `# A Simple Python program to find square  ` `# root under modulo p when p is 7, 11,  ` `# 19, 23, 31, ... etc, ` ` `  `# Returns true if square root of n under ` `# modulo p exists ` `def` `squareRoot(n, p): ` ` `  `    ``n ``=` `n ``%` `p ` `     `  `    ``# One by one check all numbers from  ` `    ``# 2 to p-1 ` `    ``for` `x ``in` `range` `(``2``, p): ` `        ``if` `((x ``*` `x) ``%` `p ``=``=` `n) : ` `            ``print``( ``"Square root is "``, x) ` `            ``return` ` `  `    ``print``( ``"Square root doesn't exist"``) ` ` `  `# Driver program to test ` `p ``=` `7` `n ``=` `2` `squareRoot(n, p) ` ` `  `# This code is Contributed by Anuj_67 `

/div>

## C#

 `// A Simple C# program to find square ` `// root under modulo p when p is 7,  ` `// 11, 19, 23, 31, ... etc, ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Returns true if square root of n ` `    ``// under modulo p exists ` `    ``static` `void` `squareRoot(``int` `n, ``int` `p) ` `    ``{ ` `        ``n = n % p; ` `     `  `        ``// One by one check all numbers ` `        ``// from 2 to p-1 ` `        ``for` `(``int` `x = 2; x < p; x++) { ` `            ``if` `((x * x) % p == n) { ` `                ``Console.Write(``"Square "` `                     ``+ ``"root is "` `+ x); ` `                ``return``; ` `            ``} ` `        ``} ` `        ``Console.Write(``"Square root "` `                   ``+ ``"doesn't exist"``); ` `    ``} ` `     `  `    ``// Driver Code ` `    ``static` `void` `Main()  ` `    ``{ ` `        ``int` `p = 7; ` `        ``int` `n = 2; ` `        ``squareRoot(n, p); ` `    ``}  ` `} ` ` `  `// This code is contributed by Anuj_67 `

## PHP

 ` `

Output:

`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 :

## C++

 `// An efficient C++ program to find square root under ` `// modulo p when p is 7, 11, 19, 23, 31, ... etc. ` `#include ` `using` `namespace` `std; ` ` `  `// Utility function to do modular exponentiation. ` `// It returns (x^y) % p. ` `int` `power(``int` `x, ``int` `y, ``int` `p) ` `{ ` `    ``int` `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; ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Returns true if square root of n under modulo p exists ` `// Assumption: p is of the form 3*i + 4 where i >= 1 ` `void` `squareRoot(``int` `n, ``int` `p) ` `{ ` `    ``if` `(p % 4 != 3) { ` `        ``cout << ``"Invalid Input"``; ` `        ``return``; ` `    ``} ` ` `  `    ``// Try "+(n^((p + 1)/4))" ` `    ``n = n % p; ` `    ``int` `x = power(n, (p + 1) / 4, p); ` `    ``if` `((x * x) % p == n) { ` `        ``cout << ``"Square root is "` `<< x; ` `        ``return``; ` `    ``} ` ` `  `    ``// Try "-(n ^ ((p + 1)/4))" ` `    ``x = p - x; ` `    ``if` `((x * x) % p == n) { ` `        ``cout << ``"Square root is "` `<< x; ` `        ``return``; ` `    ``} ` ` `  `    ``// If none of the above two work, then ` `    ``// square root doesn't exist ` `    ``cout << ``"Square root doesn't exist "``; ` `} ` ` `  `// Driver program to test ` `int` `main() ` `{ ` `    ``int` `p = 7; ` `    ``int` `n = 2; ` `    ``squareRoot(n, p); ` `    ``return` `0; ` `} `

## Java

 `// An efficient Java program to find square root under  ` `// modulo p when p is 7, 11, 19, 23, 31, ... etc.  ` `public` `class` `GFG { ` ` `  ` `  `// Utility function to do modular exponentiation.  ` `// It returns (x^y) % p.  ` `static` `int` `power(``int` `x, ``int` `y, ``int` `p)  ` `{  ` `    ``int` `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 %``2``== ``1``)  ` `            ``res = (res * x) % p;  ` ` `  `        ``// y must be even now  ` `        ``y = y >> ``1``; ``// y = y/2  ` `        ``x = (x * x) % p;  ` `    ``}  ` `    ``return` `res;  ` `}  ` ` `  `// Returns true if square root of n under modulo p exists  ` `// Assumption: p is of the form 3*i + 4 where i >= 1  ` `static` `void` `squareRoot(``int` `n, ``int` `p)  ` `{  ` `    ``if` `(p % ``4` `!= ``3``) {  ` `        ``System.out.print(``"Invalid Input"``);  ` `        ``return``;  ` `    ``}  ` ` `  `    ``// Try "+(n^((p + 1)/4))"  ` `    ``n = n % p;  ` `    ``int` `x = power(n, (p + ``1``) / ``4``, p);  ` `    ``if` `((x * x) % p == n) {  ` `        ``System.out.print(``"Square root is "` `+ x);  ` `        ``return``;  ` `    ``}  ` ` `  `    ``// Try "-(n ^ ((p + 1)/4))"  ` `    ``x = p - x;  ` `    ``if` `((x * x) % p == n) {  ` `        ``System.out.print(``"Square root is "` `+ x);  ` `        ``return``;  ` `    ``}  ` ` `  `    ``// If none of the above two work, then  ` `    ``// square root doesn't exist  ` `    ``System.out.print(``"Square root doesn't exist "``);  ` `}  ` ` `  `// Driver program to test  ` `   ``static` `public` `void` `main(String[] args) { ` `       ``int` `p = ``7``;  ` `    ``int` `n = ``2``;  ` `    ``squareRoot(n, p);  ` `    ``} ` `} `

## Python3

# 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

return res

# 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” )
return

# 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)
return

# Try “-(n ^ ((p + 1)/4))”
x = p – x
if ((x * x) % p == n):
print( “Square root is “, x )
return

# 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
squareRoot(n, p)

# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

## C#

 `// An efficient C# program to find square root under  ` `// modulo p when p is 7, 11, 19, 23, 31, ... etc.  ` ` `  `using` `System; ` `public` `class` `GFG { ` `  `  `// Utility function to do modular exponentiation.  ` `// It returns (x^y) % p.  ` `static` `int` `power(``int` `x, ``int` `y, ``int` `p)  ` `{  ` `    ``int` `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 %2 == 1)  ` `            ``res = (res * x) % p;  ` `  `  `        ``// y must be even now  ` `        ``y = y >> 1; ``// y = y/2  ` `        ``x = (x * x) % p;  ` `    ``}  ` `    ``return` `res;  ` `}  ` `  `  `// Returns true if square root of n under modulo p exists  ` `// Assumption: p is of the form 3*i + 4 where i >= 1  ` `static` `void` `squareRoot(``int` `n, ``int` `p)  ` `{  ` `    ``if` `(p % 4 != 3) {  ` `        ``Console.Write(``"Invalid Input"``);  ` `        ``return``;  ` `    ``}  ` `  `  `    ``// Try "+(n^((p + 1)/4))"  ` `    ``n = n % p;  ` `    ``int` `x = power(n, (p + 1) / 4, p);  ` `    ``if` `((x * x) % p == n) {  ` `        ``Console.Write(``"Square root is "` `+ x);  ` `        ``return``;  ` `    ``}  ` `  `  `    ``// Try "-(n ^ ((p + 1)/4))"  ` `    ``x = p - x;  ` `    ``if` `((x * x) % p == n) {  ` `        ``Console.Write(``"Square root is "` `+ x);  ` `        ``return``;  ` `    ``}  ` `  `  `    ``// If none of the above two work, then  ` `    ``// square root doesn't exist  ` `    ``Console.Write(``"Square root doesn't exist "``);  ` `}  ` `  `  `// Driver program to test  ` `   ``static` `public` `void` `Main() { ` `       ``int` `p = 7;  ` `    ``int` `n = 2;  ` `    ``squareRoot(n, p);  ` `    ``} ` `} ` `// This code is contributed by Ita_c. `

## PHP

 ` 0) ` `    ``{ ` `         `  `        ``// If y is odd, multiply ` `        ``// x with result ` `        ``if` `(``\$y` `& 1) ` `            ``\$res` `= (``\$res` `* ``\$x``) % ``\$p``; ` ` `  `        ``// y must be even now ` `        ``// y = y/2 ` `        ``\$y` `= ``\$y` `>> 1;  ` `        ``\$x` `= (``\$x` `* ``\$x``) % ``\$p``; ` `    ``} ` `    ``return` `\$res``; ` `} ` ` `  `// Returns true if square root  ` `// of n under modulo p exists ` `// Assumption: p is of the  ` `// form 3*i + 4 where i >= 1 ` `function` `squareRoot(``\$n``, ``\$p``) ` `{ ` `    ``if` `(``\$p` `% 4 != 3) ` `    ``{ ` `        ``echo` `"Invalid Input"``; ` `        ``return``;  ` `    ``} ` ` `  `    ``// Try "+(n^((p + 1)/4))" ` `    ``\$n` `= ``\$n` `% ``\$p``; ` `    ``\$x` `= power(``\$n``, (``\$p` `+ 1) / 4, ``\$p``); ` `    ``if` `((``\$x` `* ``\$x``) % ``\$p` `== ``\$n``) ` `    ``{ ` `        ``echo` `"Square root is "``, ``\$x``; ` `        ``return``; ` `    ``} ` ` `  `    ``// Try "-(n ^ ((p + 1)/4))" ` `    ``\$x` `= ``\$p` `- ``\$x``; ` `    ``if` `((``\$x` `* ``\$x``) % ``\$p` `== ``\$n``) ` `    ``{ ` `        ``echo` `"Square root is "``, ``\$x``; ` `        ``return``; ` `    ``} ` ` `  `    ``// If none of the above  ` `    ``// two work, then square ` `    ``// root doesn't exist ` `    ``echo` `"Square root doesn't exist "``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$p` `= 7; ` `    ``\$n` `= 2; ` `    ``squareRoot(``\$n``, ``\$p``); ` ` `  `// This code is contributed by ajit ` `?> `

Output:

`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

code

load comments