Рубрики

Критерий Эйлера (Проверьте, существует ли квадратный корень по модулю p)

Учитывая число 'n' и простое число p, найдите, существует или нет квадратный корень из n по модулю p. Число x является квадратным корнем из n по модулю p, если (x * x)% p = n% p.

Примеры :

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.

Наивный метод состоит в том, чтобы попробовать каждое число х, где х изменяется от 2 до р-1. Для каждого x проверьте, равен ли (x * x)% p n% p.

C ++

// Простая программа на C ++ для проверки наличия квадратного корня числа
// по модулю р существует или нет
#include<iostream>

using namespace std;

  
// Возвращает true, если существует квадратный корень из n по модулю p

bool squareRootExists(int n, int p)

{

    n = n%p;

  

    // один за другим проверяем все числа от 2 до p-1

    for (int x=2; x<p; x++)

        if ((x*x)%p == n)

            return true;

    return false;

}

  
// Программа драйвера для тестирования

int main()

{

   int p = 7;

   int n = 2;

   squareRootExists(n, p)? cout << "Yes": cout << "No";

   return 0;

}

Джава

// Простая Java-программа для проверки квадрата
// корень числа по модулю p существует или нет

class GFG 

{

      

    // Возвращает true, если квадратный корень из n под

    // по модулю p существует

    static boolean squareRootExists(int n, int p)

    {

        n = n % p;

      

        // один за другим проверяем все числа из 2

        // к п-1

        for (int x = 2; x < p; x++)

            if ((x * x) % p == n)

                return true;

                  

        return false;

    }

      

    // Программа драйвера для тестирования

    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");  

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Простая программа на Python 3 для
# проверить корень квадратный из числа
# по модулю р существует или нет

  
# Возвращает true, если квадратный корень из
# n по модулю p существует

def squareRootExists(n, p):

    n = n % p

  

    # Один за другим проверьте все номера

    № от 2 до п-1

    for x in range(2, p, 1):

        if ((x * x) % p == n):

            return True

    return False

  
Код водителя

if __name__ == '__main__':

    p = 7

    n = 2

    if(squareRootExists(n, p) == True):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// Простая программа на C # для проверки
// если квадратный корень из числа
// по модулю р существует или нет

using System;

  

class GFG

      

    // Возвращает true, если квадратный корень из

    // n по модулю p существует

    static bool squareRootExists(int n,

                                 int p)

    {

        n = n % p;

      

        // один за другим проверяем все числа

        // от 2 до п-1

        for (int x = 2; x < p; x++)

            if ((x * x) % p == n)

                return true;

                  

        return false;

    }

      

    // Код драйвера

    public static void Main () 

    {

          

        int p = 7;

        int n = 2;

          

        if(squareRootExists(n, p))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No"); 

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Простая PHP-программа для проверки
// если квадратный корень из числа
// по модулю р существует или нет

  
// Возвращает true если квадратный корень
// из n по модулю p существует

function squareRootExists($n, $p)

{

    $n = $n % $p;

  

    // один за другим проверяем все

    // числа от 2 до p-1

    for ($x = 2; $x < $p; $x++)

        if (($x * $x) % $p == $n)

            return true;

    return false;

}

  
// Код драйвера

$p = 7;

$n = 2;

if(squareRootExists($n, $p) == true)

    echo "Yes";

else

    echo "No";

  
// Этот код предоставлен ajit
?>


Выход :

Yes

Сложность времени этого метода O (p).

Эта проблема имеет прямое решение на основе критерия Эйлера.

Критерий Эйлера
гласит, что

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

Ниже приведена реализация на основе вышеуказанного критерия. См. Модульное экспонирование для функции мощности.

C ++

// C ++ программа для проверки корня квадратного числа
// по модулю р существует или нет
#include<iostream>

using namespace std;

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p.

int power(int x, int y, int p)

{

    int res = 1;     // Инициализировать результат

    x = x % p; // Обновление x, если оно больше или

               // равно p

  

    while (y > 0)

    {

        // Если y нечетно, умножаем x на результат

        if (y & 1)

            res = (res*x) % p;

  

        // у должен быть даже сейчас

        y = y>>1; // y = y / 2

        x = (x*x) % p;

    }

    return res;

}

  
// Возвращает true, если существует целое число x такое
// что (x * x)% p = n% p

bool squareRootExists(int n, int p)

{

    // Проверяем критерий Эйлера, который

    // [n ^ ((p-1) / 2)]% p равно 1 или нет.

    if (power(n, (p-1)/2, p) == 1)

       return true;

  

    return false;

}

  
// Программа драйвера для тестирования

int main()

{

   int p = 7;

   int n = 2;

   squareRootExists(n, p)? cout << "Yes": cout << "No";

   return 0;

}

Джава

// Java программа для проверки
// квадратный корень числа
// по модулю р существует или нет

import java.io.*;

  

class GFG

{

      
// Полезная функция для выполнения
// модульное возведение в степень.
// Возвращает (x ^ y)% p.

static int power(int x, int y, int p)

{

    int res = 1;     // Инициализировать результат

    x = x % p; // Обновление x, если оно больше

               // чем или равно p

  

    while (y > 0)

    {

        // Если у нечетное, умножаем

        // х с результатом

        if ((y & 1) == 0)

            res = (res * x) % p;

  

        // у должен быть даже сейчас

        y = y >> 1; // y = y / 2

        x = (x * x) % p;

    }

    return res;

}

  
// Возвращает true, если есть
// существует целое число x такое
// что (x * x)% p = n% p

static boolean squareRootExists(int n, 

                                int p)

{

    // Проверка по критерию Эйлера

    // то есть [n ^ ((p-1) / 2)]% p

    // равен 1 или нет.

    if (power(n, (p - 1) / 2, p) == 1)

    return true;

  

    return false;

}

  
// Код драйвера

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");

}
}

  
// Этот код предоставлен ajit

python3

# Python3 программа для проверки квадратного корня
№ числа по модулю р существует или нет

  
# Сервисная функция, чтобы сделать модульную
# возведение в степень. Возвращает (x ^ y)% p.

def power(x, y, p):

    res = 1 # Инициализировать результат

    x = x % p

      

    # Обновите x, если оно больше

    # или равно p

    while (y > 0):

          

        # Если у нечетно, умножить

        # х с результатом

        if (y & 1):

            res = (res * x) % p

              

        # у должно быть даже сейчас

        y = y >> 1 # y = y / 2

        x = (x * x) % p

    return res

  
# Возвращает true, если существует целое число
# x такое, что (x * x)% p = n% p

def squareRootExists(n, p):

      

    # Проверьте критерий Эйлера, который

    # [n ^ ((p-1) / 2)]% p равно 1 или нет.

    if (power(n, (int)((p - 1) / 2), p) == 1):

        return True

    return False

  
Код водителя

p = 7

n = 2

if(squareRootExists(n, p) == True):

    print("Yes")

else:

    print("No")

  
# Этот код предоставлен Rajput-Ji

C #

// C # программа для проверки
// квадратный корень числа
// по модулю р существует или нет

using System;

  

class GFG

{

      
// Полезная функция для выполнения
// модульное возведение в степень.
// Возвращает (x ^ y)% p.

static int power(int x, 

                 int y, int p)

{

    int res = 1;// Инициализировать результат

    x = x % p;  // Обновление x, если оно больше

                // чем или равно p

  

    while (y > 0)

    {

        // Если у нечетное, умножаем

        // х с результатом

        if ((y & 1) == 0)

            res = (res * x) % p;

  

        // у должен быть даже сейчас

        y = y >> 1; // y = y / 2

        x = (x * x) % p;

    }

    return res;

}

  
// Возвращает true, если есть
// существует целое число x такое
// что (x * x)% p = n% p

static bool squareRootExists(int n, 

                             int p)

{

    // Проверка по критерию Эйлера

    // то есть [n ^ ((p-1) / 2)]% p

    // равен 1 или нет.

    if (power(n, (p - 1) / 2, p) == 1)

    return true;

  

    return false;

}

  
// Код драйвера

static public void Main ()

{

    int p = 7;

    int n = 2;

    if(squareRootExists(n, p))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No");

}
}

  
// Этот код предоставлен m_kit

PHP

<?php
// PHP программа для проверки
// если квадратный корень из
// номер по модулю
// р существует или нет

  
// Функция полезности для
// делаем модульное возведение в степень
// Возвращает (x ^ y)% p.

function power($x, $y, $p)

{

    $res = 1; // Инициализировать результат

    $x = $x % $p; // Обновить х, если это

                  // больше чем

                  // или равно p

  

    while ($y > 0)

    {

        // Если у нечетное, умножаем

        // х с результатом

        if ($y & 1)

            $res = ($res

                    $x) % $p;

  

        // у должен быть даже сейчас

        $y = $y >> 1; // y = y / 2

        $x = ($x * $x) % $p;

    }

    return $res;

}

  
// Возвращает true, если есть
// существует целое число x такое
// что (x * x)% p = n% p

function squareRootExists($n, $p)

{

    // Проверка по критерию Эйлера

    // то есть [n ^ ((p-1) / 2)]% p

    // равен 1 или нет.

    if (power($n, (int)(($p - 1) / 2), 

                         $p) == 1)

    return true;

  

    return false;

}

  
// Код драйвера

$p = 7;

$n = 2;

  

if(squareRootExists($n, $p) == true)

    echo "Yes";

else

    echo "No";

  
// Этот код предоставлен ajit
?>


Выход :

Yes

Как это работает?

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  

Временная сложность этого метода, основанного на критериях Эйлера, равна O (Log p)

Вы можете увидеть ниже:
Найти квадратный корень по модулю р | Установите 1 (когда р в форме 4 * я + 3)

Эта статья пополняемые Шивов Гупт. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Критерий Эйлера (Проверьте, существует ли квадратный корень по модулю p)

0.00 (0%) 0 votes