Рубрики

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

Для заданного числа n и простого числа p найдите корень квадратный из n по модулю p, если он существует. Можно сказать, что p находится в форме для 4 * i + 3 (ИЛИ p% 4 = 3), где i является целым числом. Примерами таких простых чисел являются 7, 11, 19, 23, 31,… и т. Д.,

Примеры:

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

Наивное решение: Попробуйте все числа от 2 до p-1. И для каждого числа x проверьте, является ли x квадратным корнем из n по модулю p.

C ++

// Простая программа на C ++ для поиска квадратного корня по модулю p
// когда p равно 7, 11, 19, 23, 31, ... и т. д.,
#include <iostream>

using namespace std;

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

void squareRoot(int n, int p)

{

    n = n % p;

  

    // один за другим проверяем все числа от 2 до 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";

}

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

int main()

{

    int p = 7;

    int n = 2;

    squareRoot(n, p);

    return 0;

}

Джава

// Простая Java-программа для поиска квадрата
// корень по модулю p, когда p равно 7,
// 11, 19, 23, 31, ... и т. Д.,

import java .io.*;

  

class GFG {

  

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

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

    static void squareRoot(int n, int p)

    {

        n = n % p;

      

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

        // от 2 до п-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");

    }

      

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

    public static void main(String[] args) 

    {

        int p = 7;

        int n = 2;

        squareRoot(n, p);

    

}

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

python3

# Простая программа на Python для поиска квадрата
# корень по модулю р, когда р 7, 11,
№ 19, 23, 31, ... и т. Д.,

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

def squareRoot(n, p):

  

    n = n % p

      

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

    № 2 до п-1

    for x in range (2, p):

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

            print( "Square root is ", x)

            return

  

    print( "Square root doesn't exist")

  
# Драйвер программы для тестирования

p = 7

n = 2

squareRoot(n, p)

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

C #

// Простая C # программа для поиска квадрата
// корень по модулю p, когда p равно 7,
// 11, 19, 23, 31, ... и т. Д.,

using System;

  

class GFG {

  

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

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

    static void squareRoot(int n, int p)

    {

        n = n % p;

      

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

        // от 2 до п-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");

    }

      

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

    static void Main() 

    {

        int p = 7;

        int n = 2;

        squareRoot(n, p);

    

}

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

PHP

<?php
// Простая PHP-программа для поиска
// квадратный корень по модулю p
// когда p равно 7, 11, 19, 23, 31,
// ... и т.д,

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

function squareRoot($n, $p)

{

    $n = $n % $p;

  

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

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

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

    {

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

        {

            echo("Square root is " . $x);

            return;

        }

    }

    echo("Square root doesn't exist");

}

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

$p = 7;

$n = 2;

squareRoot($n, $p);

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


Выход:

Square root is 3

Сложность времени этого решения O (p)

Прямой метод: если p имеет форму 3 * i + 4, то существует быстрый способ поиска квадратного корня.

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

Ниже приведена реализация вышеуказанной идеи:

C ++

// Эффективная программа на C ++ для поиска квадратного корня под
// по модулю p, когда p равно 7, 11, 19, 23, 31, ... и т. д.
#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, если существует квадратный корень из n по модулю p
// Предположение: p имеет вид 3 * i + 4, где i> = 1

void squareRoot(int n, int p)

{

    if (p % 4 != 3) {

        cout << "Invalid Input";

        return;

    }

  

    // Попробуйте "+ (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;

    }

  

    // Попробуйте "- (n ^ ((p + 1) / 4))"

    x = p - x;

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

        cout << "Square root is " << x;

        return;

    }

  

    // Если ни одна из двух вышеперечисленных не работает, то

    // квадратный корень не существует

    cout << "Square root doesn't exist ";

}

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

int main()

{

    int p = 7;

    int n = 2;

    squareRoot(n, p);

    return 0;

}

Джава

// Эффективная Java-программа для поиска квадратного корня под
// по модулю p, когда p равно 7, 11, 19, 23, 31, ... и т. д.

public 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) { 

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

        if (y %2== 1

            res = (res * x) % p; 

  

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

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

        x = (x * x) % p; 

    

    return res; 

  
// Возвращает true, если существует квадратный корень из n по модулю p
// Предположение: p имеет вид 3 * i + 4, где i> = 1

static void squareRoot(int n, int p) 

    if (p % 4 != 3) { 

        System.out.print("Invalid Input"); 

        return

    

  

    // Попробуйте "+ (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

    

  

    // Попробуйте "- (n ^ ((p + 1) / 4))"

    x = p - x; 

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

        System.out.print("Square root is " + x); 

        return

    

  

    // Если ни одна из двух вышеперечисленных не работает, то

    // квадратный корень не существует

    System.out.print("Square root doesn't exist "); 

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

   static public void main(String[] args) {

       int p = 7

    int n = 2

    squareRoot(n, p); 

    }

}

python3

# Эффективная программа на python3 для поиска квадратного корня
# по модулю p, когда p равно 7, 11, 19, 23, 31, ... и т. д.

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

def power(x, y, p) :

  

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

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

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

  

    while (y > 0): 

          

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

        if (y & 1):

            res = (res * x) %

  

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

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

        x = (x * x) %

  

    return res 

  
# Возвращает true, если квадратный корень из n под
# по модулю p существует. Предположение: р
# form 3 * i + 4, где i> = 1

def squareRoot(n, p): 

  

    if (p % 4 != 3) : 

        print( "Invalid Input" )

        return

  

  

    # Попробуйте "+ (n ^ ((p + 1) / 4))"

    n = n %

    x = power(n, (p + 1) // 4, p) 

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

        print( "Square root is ", x) 

        return

  

    # Попробуйте "- (n ^ ((p + 1) / 4))"

    x = p -

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

        print( "Square root is ", x )

        return

  

    # Если ни один из вышеперечисленных двух не работает

    # квадратный корень не существует

    print( "Square root doesn't exist " )

  
Код водителя

p = 7

n = 2

squareRoot(n, p) 

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// Эффективная программа на C # для поиска квадратного корня под
// по модулю p, когда p равно 7, 11, 19, 23, 31, ... и т. д.

  

using System;

public 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) { 

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

        if (y %2 == 1) 

            res = (res * x) % p; 

   

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

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

        x = (x * x) % p; 

    

    return res; 

   
// Возвращает true, если существует квадратный корень из n по модулю p
// Предположение: p имеет вид 3 * i + 4, где i> = 1

static void squareRoot(int n, int p) 

    if (p % 4 != 3) { 

        Console.Write("Invalid Input"); 

        return

    

   

    // Попробуйте "+ (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

    

   

    // Попробуйте "- (n ^ ((p + 1) / 4))"

    x = p - x; 

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

        Console.Write("Square root is " + x); 

        return

    

   

    // Если ни одна из двух вышеперечисленных не работает, то

    // квадратный корень не существует

    Console.Write("Square root doesn't exist "); 

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

   static public void Main() {

       int p = 7; 

    int n = 2; 

    squareRoot(n, p); 

    }

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

PHP

<?php
// Эффективная программа PHP
// найти квадратный корень под
// по модулю p, когда p равно 7, 11,
// 19, 23, 31, ... и т. Д.

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

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

{

      

    // Инициализировать результат

    $res = 1;     

      

    // Обновить х, если это

    // больше или

    // равно p

    $x = $x % $p

  

    while ($y > 0)

    {

          

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

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

        if ($y & 1)

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

  

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

        // y = y / 2

        $y = $y >> 1; 

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

    }

    return $res;

}

  
// Возвращает true если квадратный корень
// из n по модулю p существует
// Предположение: р
// форма 3 * i + 4, где i> = 1

function squareRoot($n, $p)

{

    if ($p % 4 != 3)

    {

        echo "Invalid Input";

        return

    }

  

    // Попробуйте "+ (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;

    }

  

    // Попробуйте "- (n ^ ((p + 1) / 4))"

    $x = $p - $x;

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

    {

        echo "Square root is ", $x;

        return;

    }

  

    // Если ничего из вышеперечисленного

    // две работы, затем квадрат

    // корень не существует

    echo "Square root doesn't exist ";

}

  

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

    $p = 7;

    $n = 2;

    squareRoot($n, $p);

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


Выход:

Square root is 4

Сложность времени этого решения O (Log p)

Как это работает?
Мы обсуждали критерий Эйлера в предыдущем посте.

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]

Мы скоро будем обсуждать методы, когда p не находится в вышеуказанной форме.

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

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

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

0.00 (0%) 0 votes