Tutorialspoint.dev

Euler’s criterion (Check if square root under modulo p exists)

Given a number ‘n’ and a prime p, find if square root of n under modulo p exists or not. A number x is square root of n under modulo p if (x*x)%p = n%p.

Examples :

Input:   n = 2, p = 5
Output:  false
There doesn't exist a number x such that 
(x*x)%5 is 2

Input:   n = 2, p = 7
Output:  true
There exists a number x such that (x*x)%7 is
2.  The number is 3.

A Naive Method is to try every number x where x varies from 2 to p-1. For every x, check if (x * x) % p is equal to n % p.



C++

// A Simple C++ program to check if square root of a number
// under modulo p exists or not
#include<iostream>
using namespace std;
  
// Returns true if square root of n under modulo p exists
bool squareRootExists(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)
            return true;
    return false;
}
  
// Driver program to test
int main()
{
   int p = 7;
   int n = 2;
   squareRootExists(n, p)? cout << "Yes": cout << "No";
   return 0;
}

Java

// A Simple Java program to check if square 
// root of a number under modulo p exists or not
class GFG 
{
      
    // Returns true if square root of n under 
    // modulo p exists
    static boolean squareRootExists(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)
                return true;
                  
        return false;
    }
      
    // Driver program to test
    public static void main (String[] args) 
    {
          
        int p = 7;
        int n = 2;
          
        if(squareRootExists(n, p))
            System.out.print("Yes");
        else
            System.out.print("No");  
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# A Simple Python 3 program to 
# check if square root of a number
# under modulo p exists or not
  
# Returns true if square root of
# n under modulo p exists
def squareRootExists(n, p):
    n = n % p
  
    # One by one check all numbers 
    # from 2 to p-1
    for x in range(2, p, 1):
        if ((x * x) % p == n):
            return True
    return False
  
# Driver Code
if __name__ == '__main__':
    p = 7
    n = 2
    if(squareRootExists(n, p) == True):
        print("Yes")
    else:
        print("No")
  
# This code is contributed by
# Surendra_Gangwar

C#

// A Simple C# program to check
// if square root of a number 
// under modulo p exists or not
using System;
  
class GFG
      
    // Returns true if square root of  
    // n under modulo p exists
    static bool squareRootExists(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)
                return true;
                  
        return false;
    }
      
    // Driver code
    public static void Main () 
    {
          
        int p = 7;
        int n = 2;
          
        if(squareRootExists(n, p))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No"); 
    }
}
  
// This code is contributed by Sam007.

/div>

PHP

<?php
// A Simple PHP program to check 
// if square root of a number
// under modulo p exists or not
  
// Returns true if square root 
// of n under modulo p exists
function squareRootExists($n, $p)
{
    $n = $n % $p;
  
    // One by one check all
    // numbers from 2 to p-1
    for ($x = 2; $x < $p; $x++)
        if (($x * $x) % $p == $n)
            return true;
    return false;
}
  
// Driver Code
$p = 7;
$n = 2;
if(squareRootExists($n, $p) == true)
    echo "Yes";
else
    echo "No";
  
// This code is contributed by ajit
?>


Output :

Yes

Time Complexity of this method is O(p).

This problem has a direct solution based on Euler’s Criterion.

Euler’s criterion
states that

Square root of n under modulo p exists if and only if
n(p-1)/2 % p = 1

Here square root of n exists means is, there exist
an integer x such that (x * x) % p = 1

Below is implementation based on above criterion. Refer Modular Exponentiation for power function.



C++

// C++ program to check if square root of a number
// under modulo p exists or not
#include<iostream>
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 there exists an integer x such 
// that (x*x)%p = n%p
bool squareRootExists(int n, int p)
{
    // Check for Euler's criterion that is
    // [n ^ ((p-1)/2)] % p is 1 or not.
    if (power(n, (p-1)/2, p) == 1)
       return true;
  
    return false;
}
  
// Driver program to test
int main()
{
   int p = 7;
   int n = 2;
   squareRootExists(n, p)? cout << "Yes": cout << "No";
   return 0;
}

Java

// Java program to check if
// square root of a number
// under modulo p exists or not
import java.io.*;
  
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 & 1) == 0)
            res = (res * x) % p;
  
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
  
// Returns true if there
// exists an integer x such 
// that (x*x)%p = n%p
static boolean squareRootExists(int n, 
                                int p)
{
    // Check for Euler's criterion 
    // that is [n ^ ((p-1)/2)] % p
    // is 1 or not.
    if (power(n, (p - 1) / 2, p) == 1)
    return true;
  
    return false;
}
  
// Driver Code
public static void main (String[] args) 
{
    int p = 7;
    int n = 2;
    if(squareRootExists(n, p))
        System.out.println ("Yes");
    else
        System.out.println("No");
}
}
  
// This code is contributed by ajit 

Python3

# Python3 program to check if square root 
# of a number under modulo p exists or not
  
# 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 there exists an integer
# x such that (x*x)%p = n%p
def squareRootExists(n, p):
      
    # Check for Euler's criterion that is 
    # [n ^ ((p-1)/2)] % p is 1 or not.
    if (power(n, (int)((p - 1) / 2), p) == 1):
        return True
    return False
  
# Driver Code
p = 7
n = 2
if(squareRootExists(n, p) == True):
    print("Yes")
else:
    print("No")
  
# This code is contributed by Rajput-Ji

C#

// C# program to check if
// square root of a number
// under modulo p exists or not
using System;
  
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 & 1) == 0)
            res = (res * x) % p;
  
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
  
// Returns true if there
// exists an integer x such 
// that (x*x)%p = n%p
static bool squareRootExists(int n, 
                             int p)
{
    // Check for Euler's criterion 
    // that is [n ^ ((p-1)/2)] % p
    // is 1 or not.
    if (power(n, (p - 1) / 2, p) == 1)
    return true;
  
    return false;
}
  
// Driver Code
static public void Main ()
{
    int p = 7;
    int n = 2;
    if(squareRootExists(n, p))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
  
// This code is contributed by m_kit

PHP

<?php
// PHP program to check 
// if square root of a 
// number under modulo 
// p exists or not
  
// Utility function to 
// do modular exponentiation 
// It returns (x^y) % p.
function 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 there 
// exists an integer x such 
// that (x*x)%p = n%p
function squareRootExists($n, $p)
{
    // Check for Euler's criterion 
    // that is [n ^ ((p-1)/2)] % p 
    // is 1 or not.
    if (power($n, (int)(($p - 1) / 2), 
                         $p) == 1)
    return true;
  
    return false;
}
  
// Driver Code
$p = 7;
$n = 2;
  
if(squareRootExists($n, $p) == true)
    echo "Yes";
else
    echo "No";
  
// This code is contributed by ajit
?>


Output :

Yes

How does this work?

If p is a prime, then it must be an odd number and (p-1) 
must be an even, i.e., (p-1)/2 must be an integer.

Suppose a square root of n under modulo p exists, then
there must exist an integer x such that,
      x2 % p = n % p 
or, 
     x2 ? n mod p

Raising both sides to power (p-1)/2,
      (x2)(p-1)/2 ? n(p-1)/2 mod p           
      xp-1 ? n(p-1)/2 mod p

Since p is a prime, from Fermet's theorem, we can say that 
   xp-1 ? 1 mod p

Therefore,
  n(p-1)/2 ? 1 mod p  

Time complexity of this Euler Criterion based method is O(Log p)

You may like to see below:
Find Square Root under Modulo p | Set 1 (When p is in form of 4*i + 3)



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter