Рубрики

Найти квадратный корень по модулю р | Набор 2 (алгоритм Шенкса Тонелли)

Для заданного числа n и простого числа p найдите корень квадратный из n по модулю p, если он существует.
Примеры:

Input: n = 2, p = 113
Output: 62
62^2 = 3844  and  3844 % 113 = 2

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

Мы обсудили критерий Эйлера, чтобы проверить, существует квадратный корень или нет. Мы также обсудили решение, которое работает только тогда, когда р в форме 4 * я + 3

В этом посте обсуждается алгоритм Шенк Тонелли, который работает для всех типов входов.

Шаги алгоритма для нахождения модульного квадратного корня с помощью алгоритма хвостовика Тонелли:

1) Вычислить n ^ ((p — 1) / 2) (mod p), это должно быть 1 или p-1, если это p-1, то модульный квадратный корень невозможен.

2) Затем после записи p-1 как (s * 2 ^ e) для некоторого целого числа s и e, где s должно быть нечетным числом, а s и e должны быть положительными.

3) Затем найдите число q такое, что q ^ ((p — 1) / 2) (mod p) = -1

4) Инициализируйте переменные x, b, g и r следующими значениями

   x = n ^ ((s + 1) / 2 (first guess of square root)
   b = n ^ s                
   g = q ^ s
   r = e   (exponent e will decrease after each updation) 

5) Теперь выполните цикл до m> 0 и обновите значение x, что будет нашим окончательным ответом.

   Find least integer m such that b^(2^m) = 1(mod p)  and  0 <= m <= r – 1 
   If m = 0, then we found correct answer and return x as result
   Else update x, b, g, r as below
       x = x * g ^ (2 ^ (r – m - 1))
       b = b * g ^(2 ^ (r - m))
       g = g ^ (2 ^ (r - m))
       r = m 

поэтому, если m становится 0 или b становится 1, мы завершаем работу и печатаем результат. Этот цикл гарантирует завершение, потому что значение m уменьшается каждый раз после обновления.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для реализации алгоритма Шенкса Тонелли для
// нахождение модульных квадратных корней
#include <bits/stdc++.h>

using namespace std;

  
// функция полезности, чтобы найти pow (base, exponent)% модуль

int pow(int base, int exponent, int modulus)

{

    int result = 1;

    base = base % modulus;

    while (exponent > 0)

    {

        if (exponent % 2 == 1)

           result = (result * base)% modulus;

        exponent = exponent >> 1;

        base = (base * base) % modulus;

    }

    return result;

}

  
// утилита для поиска gcd

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    else

        return gcd(b, a % b);

}

  
// Возвращает k такое, что b ^ k = 1 (mod p)

int order(int p, int b)

{

    if (gcd(p, b) != 1)

    {

        printf("p and b are not co-prime.\n");

        return -1;

    }

  

    // Инициализация k с первым нечетным простым числом

    int k = 3;

    while (1)

    {

        if (pow(b, k, p) == 1)

            return k;

        k++;

    }

}

  
// функция возвращает p - 1 (= x аргумент) как x * 2 ^ e,
// где x будет нечетным, посылая e в качестве ссылки, потому что
// обновление требуется в реальном времени

int convertx2e(int x, int& e)

{

    e = 0;

    while (x % 2 == 0)

    {

        x /= 2;

        e++;

    }

    return x;

}

  
// Основная функция для нахождения модульного квадратного корня

int STonelli(int n, int p)

{

    // a и p должны быть взаимно просты для нахождения модульного

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

    if (gcd(n, p) != 1)

    {

        printf("a and p are not coprime\n");

        return -1;

    }

  

    // Если выражение ниже return (p - 1), то модульное

    // квадратный корень невозможен

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

    {

        printf("no sqrt possible\n");

        return -1;

    }

  

    // выражая p - 1, в терминах s * 2 ^ e, где s

    // нечетное число

    int s, e;

    s = convertx2e(p - 1, e);

  

    // найти наименьшее q такое, что q ^ ((p - 1) / 2)

    // (mod p) = p - 1

    int q;

    for (q = 2; ; q++)

    {

        // q - 1 вместо (-1% p)

        if (pow(q, (p - 1) / 2, p) == (p - 1))

            break;

    }

  

    // Инициализация переменных x, b и g

    int x = pow(n, (s + 1) / 2, p);

    int b = pow(n, s, p);

    int g = pow(q, s, p);

  

    int r = e;

  

    // продолжаем цикл пока b не станет 1 или m не станет 0

    while (1)

    {

        int m;

        for (m = 0; m < r; m++)

        {

            if (order(p, b) == -1)

                return -1;

  

            // найти m такой, что b ^ (2 ^ m) = 1

            if (order(p, b) == pow(2, m))

                break;

        }

        if (m == 0)

            return x;

  

        // обновляем значения x, g и b согласно

        // алгоритм

        x = (x * pow(g, pow(2, r - m - 1), p)) % p;

        g = pow(g, pow(2, r - m), p);

        b = (b * g) % p;

  

        if (b == 1)

            return x;

        r = m;

    }

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int n = 2;

  

    // р должно быть простым

    int p = 113;

  

    int x = STonelli(n, p);

  

    if (x == -1)

        printf("Modular square root is not exist\n");

    else

        printf("Modular square root of %d and %d is %d\n",

                n, p, x);

}

Джава

// Java-программа для реализации Shanks
// алгоритм Тонелли для нахождения
// Модульные квадратные корни

class GFG

{

    static int z = 0;

      
// полезная функция для поиска
// pow (base, экспонента)% модуль

static int pow1(int base1, 

    int exponent, int modulus) 

    int result = 1

    base1 = base1 % modulus; 

    while (exponent > 0

    

        if (exponent % 2 == 1

            result = (result * base1) % modulus; 

        exponent = exponent >> 1

        base1 = (base1 * base1) % modulus; 

    

    return result; 

  
// утилита для поиска gcd

static int gcd(int a, int b) 

    if (b == 0

        return a; 

    else

        return gcd(b, a % b); 

  
// Возвращает k такое, что b ^ k = 1 (mod p)

static int order(int p, int b) 

    if (gcd(p, b) != 1

    

        System.out.println("p and b are"

                            "not co-prime."); 

        return -1

    

  

    // Инициализация k с первым

    // нечетное простое число

    int k = 3

    while (true

    

        if (pow1(b, k, p) == 1

            return k; 

        k++; 

    

  
// функция возвращает p - 1 (= x аргумент)
// как x * 2 ^ e, где x будет нечетным
// отправка e в качестве ссылки, потому что
// обновление требуется в реальном времени

static int convertx2e(int x) 

    z = 0;

    while (x % 2 == 0

    

        x /= 2

        z++; 

    

    return x; 

  
// Основная функция для поиска
// модульный квадратный корень

static int STonelli(int n, int p) 

    // a и p должны быть взаимно просты для

    // найти модульный квадратный корень

    if (gcd(n, p) != 1

    

        System.out.println("a and p are not coprime"); 

        return -1

    

  

    // Если выражение ниже return (p - 1), то модульное

    // квадратный корень невозможен

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

    

        System.out.println("no sqrt possible"); 

        return -1

    

  

    // выражая p - 1, в терминах

    // s * 2 ^ e, где s нечетное число

    int s, e; 

    s = convertx2e(p - 1);

    e = z;

  

    // найти наименьшее q такое, что q ^ ((p - 1) / 2)

    // (mod p) = p - 1

    int q; 

    for (q = 2; ; q++) 

    

        // q - 1 вместо (-1% p)

        if (pow1(q, (p - 1) / 2, p) == (p - 1)) 

            break

    

  

    // Инициализация переменных x, b и g

    int x = pow1(n, (s + 1) / 2, p); 

    int b = pow1(n, s, p); 

    int g = pow1(q, s, p); 

  

    int r = e; 

  

    // продолжаем цикл до b

    // становится 1 или m становится 0

    while (true

    

        int m; 

        for (m = 0; m < r; m++) 

        

            if (order(p, b) == -1

                return -1

  

            // найти m такой, что b ^ (2 ^ m) = 1

            if (order(p, b) == Math.pow(2, m)) 

                break

        

        if (m == 0

            return x; 

  

        // обновляем значения x, g и b

        // согласно алгоритму

        x = (x * pow1(g, (int)Math.pow(2

                            r - m - 1), p)) % p; 

        g = pow1(g, (int)Math.pow(2, r - m), p); 

        b = (b * g) % p; 

  

        if (b == 1

            return x; 

        r = m; 

    

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

public static void main (String[] args) 

{

  

    int n = 2

  

    // р должно быть простым

    int p = 113

  

    int x = STonelli(n, p); 

  

    if (x == -1)

        System.out.println("Modular square"

                        "root is not exist\n"); 

    else

        System.out.println("Modular square root of " +

                            n + " and " + p + " is " +

                            x + "\n"); 


}

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

python3

# Python3 программа для реализации Shanks Tonelli
# алгоритм нахождения модульных квадратных корней

  
# полезная функция для поиска pow (base,
# экспонента)% модуль

def pow1(base, exponent, modulus): 

  

    result = 1

    base = base % modulus; 

    while (exponent > 0): 

        if (exponent % 2 == 1):

            result = (result * base) % modulus; 

        exponent = int(exponent) >> 1

        base = (base * base) % modulus; 

  

    return result; 

  
# служебная функция для поиска gcd

def gcd(a, b): 

    if (b == 0): 

        return a; 

    else:

        return gcd(b, a % b); 

  
# Возвращает k такое, что b ^ k = 1 (mod p)

def order(p, b): 

  

    if (gcd(p, b) != 1):

        print("p and b are not co-prime.\n"); 

        return -1

  

    # Инициализация k с первым

    # нечетное простое число

    k = 3

    while (True): 

        if (pow1(b, k, p) == 1): 

            return k; 

        k += 1

  
# функция возвращает p - 1 (= x аргумент) как
# x * 2 ^ e, где x будет нечетной отправкой e
# в качестве ссылки, потому что требуется обновление
# в фактическом е

def convertx2e(x):

    z = 0

    while (x % 2 == 0):

        x = x / 2

        z += 1

          

    return [x, z]; 

  
# Основная функция для поиска
# модульный квадратный корень

def STonelli(n, p): 

  

    # a и p должны быть взаимно простыми для

    # найти модульный квадратный корень

    if (gcd(n, p) != 1):

        print("a and p are not coprime\n"); 

        return -1

  

    # Если выражение ниже возврата (p - 1), то

    # модульный квадратный корень невозможен

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

        print("no sqrt possible\n"); 

        return -1

  

    # выражая p - 1, в терминах s * 2 ^ e,

    # где s нечетное число

    ar = convertx2e(p - 1);

    s = ar[0];

    e = ar[1];

  

    # найти наименьшее q такое, что

    # q ^ ((p - 1) / 2) (mod p) = p - 1

    q = 2

    while (True):

          

        # q - 1 вместо (-1% p)

        if (pow1(q, (p - 1) / 2, p) == (p - 1)): 

            break;

        q += 1;

  

    # Инициализация переменных x, b и g

    x = pow1(n, (s + 1) / 2, p); 

    b = pow1(n, s, p); 

    g = pow1(q, s, p); 

  

    r = e; 

  

    # продолжайте цикл пока b не станет

    # 1 или m становится 0

    while (True):

        m = 0

        while (m < r):

            if (order(p, b) == -1): 

                return -1

  

            # найти m такой, что b ^ (2 ^ m) = 1

            if (order(p, b) == pow(2, m)): 

                break;

            m += 1;

  

        if (m == 0): 

            return x; 

  

        # обновление значений x, g и b

        # согласно алгоритму

        x = (x * pow1(g, pow(2, r - m - 1), p)) % p; 

        g = pow1(g, pow(2, r - m), p); 

        b = (b * g) % p; 

  

        if (b == 1): 

            return x; 

        r = m; 

  
Код водителя

n = 2

  
# p должно быть простым

p = 113

  

x = STonelli(n, p); 

  

if (x == -1): 

    print("Modular square root is not exist\n"); 

else:

    print("Modular square root of", n, 

          "and", p, "is", x); 

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

C #

// C # программа для реализации Шенкса
// алгоритм Тонелли для нахождения
// Модульные квадратные корни

using System;

  

class GFG

{

      

static int z=0;

      
// полезная функция для поиска
// pow (base, экспонента)% модуль

static int pow1(int base1, 

        int exponent, int modulus) 

    int result = 1; 

    base1 = base1 % modulus; 

    while (exponent > 0) 

    

        if (exponent % 2 == 1) 

            result = (result * base1) % modulus; 

        exponent = exponent >> 1; 

        base1 = (base1 * base1) % modulus; 

    

    return result; 

  
// утилита для поиска gcd

static int gcd(int a, int b) 

    if (b == 0) 

        return a; 

    else

        return gcd(b, a % b); 

  
// Возвращает k такое, что b ^ k = 1 (mod p)

static int order(int p, int b) 

    if (gcd(p, b) != 1) 

    

        Console.WriteLine("p and b are" +

                            "not co-prime."); 

        return -1; 

    

  

    // Инициализация k с помощью

    // первое нечетное простое число

    int k = 3; 

    while (true

    

        if (pow1(b, k, p) == 1) 

            return k; 

        k++; 

    

  
// функция возвращает p - 1 (= x аргумент)
// как x * 2 ^ e, где x будет нечетной отправкой
// e как ссылка, потому что обновление
// необходимо в фактическом е

static int convertx2e(int x) 

    z = 0;

    while (x % 2 == 0) 

    

        x /= 2; 

        z++; 

    

    return x; 

  
// Основная функция для поиска
// модульный квадратный корень

static int STonelli(int n, int p) 

    // a и p должны быть взаимно просты для

    // найти модульный квадратный корень

    if (gcd(n, p) != 1) 

    

        Console.WriteLine("a and p are not coprime"); 

        return -1; 

    

  

    // Если выражение ниже возврата (p - 1), тогда

    // модульный квадратный корень невозможен

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

    

        Console.WriteLine("no sqrt possible"); 

        return -1; 

    

  

    // выражая p - 1, в терминах s * 2 ^ e,

    // где s нечетное число

    int s, e; 

    s = convertx2e(p - 1);

    e=z;

  

    // найти наименьшее q такое, что q ^ ((p - 1) / 2)

    // (mod p) = p - 1

    int q; 

    for (q = 2; ; q++) 

    

        // q - 1 вместо (-1% p)

        if (pow1(q, (p - 1) / 2, p) == (p - 1)) 

            break

    

  

    // Инициализация переменных x, b и g

    int x = pow1(n, (s + 1) / 2, p); 

    int b = pow1(n, s, p); 

    int g = pow1(q, s, p); 

  

    int r = e; 

  

    // продолжаем цикл пока b не станет

    // 1 или m становится 0

    while (true

    

        int m; 

        for (m = 0; m < r; m++) 

        

            if (order(p, b) == -1) 

                return -1; 

  

            // найти m такой, что b ^ (2 ^ m) = 1

            if (order(p, b) == Math.Pow(2, m)) 

                break

        

        if (m == 0) 

            return x; 

  

        // обновляем значения x, g и b

        // согласно алгоритму

        x = (x * pow1(g, (int)Math.Pow(2, r - m - 1), p)) % p; 

        g = pow1(g, (int)Math.Pow(2, r - m), p); 

        b = (b * g) % p; 

  

        if (b == 1) 

            return x; 

        r = m; 

    

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

static void Main() 

    int n = 2; 

  

    // р должно быть простым

    int p = 113; 

  

    int x = STonelli(n, p); 

  

    if (x == -1)

        Console.WriteLine("Modular square root" +

                            "is not exist\n"); 

    else

        Console.WriteLine("Modular square root of"

                        "{0} and {1} is {2}\n", n, p, x); 


}

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

PHP

<?php
// PHP-программа для реализации Шанкса Тонелли
// алгоритм нахождения модульных квадратных корней

  
// функция полезности для поиска pow (base,
// экспонента)% модуль

function pow1($base, $exponent, $modulus

    $result = 1; 

    $base = $base % $modulus

    while ($exponent > 0) 

    

        if ($exponent % 2 == 1) 

        $result = ($result * $base) % $modulus

        $exponent = $exponent >> 1; 

        $base = ($base * $base) % $modulus

    

    return $result

  
// утилита для поиска gcd

function gcd($a, $b

    if ($b == 0) 

        return $a

    else

        return gcd($b, $a % $b); 

  
// Возвращает k такое, что b ^ k = 1 (mod p)

function order($p, $b

    if (gcd($p, $b) != 1) 

    

        print("p and b are not co-prime.\n"); 

        return -1; 

    

  

    // Инициализация k с первым

    // нечетное простое число

    $k = 3; 

    while (1) 

    

        if (pow1($b, $k, $p) == 1) 

            return $k

        $k++; 

    

  
// функция возвращает p - 1 (= x аргумент) как
// x * 2 ^ e, где x будет нечетной отправкой e
// как ссылка, потому что требуется обновление
// в фактическом е

function convertx2e($x, &$e

    $e = 0; 

    while ($x % 2 == 0) 

    

        $x = (int)($x / 2); 

        $e++; 

    

    return $x

  
// Основная функция для нахождения
// модульный квадратный корень

function STonelli($n, $p

    // a и p должны быть взаимно просты для

    // найти модульный квадратный корень

    if (gcd($n, $p) != 1) 

    

        print("a and p are not coprime\n"); 

        return -1; 

    

  

    // Если выражение ниже возврата (p - 1), тогда

    // модульный квадратный корень невозможен

    if (pow1($n, ($p - 1) / 2, $p) == ($p - 1)) 

    

        printf("no sqrt possible\n"); 

        return -1; 

    

  

    // выражая p - 1, в терминах s * 2 ^ e,

    // где s нечетное число

    $e = 0; 

    $s = convertx2e($p - 1, $e); 

  

    // найти наименьшее q такое, что

    // q ^ ((p - 1) / 2) (mod p) = p - 1

    $q = 2; 

    for (; ; $q++) 

    

        // q - 1 вместо (-1% p)

        if (pow1($q, ($p - 1) / 2, $p) == ($p - 1)) 

            break

    

  

    // Инициализация переменных x, b и g

    $x = pow1($n, ($s + 1) / 2, $p); 

    $b = pow1($n, $s, $p); 

    $g = pow1($q, $s, $p); 

  

    $r = $e

  

    // продолжаем цикл пока b не станет

    // 1 или m становится 0

    while (1) 

    

        $m = 0; 

        for (; $m < $r; $m++) 

        

            if (order($p, $b) == -1) 

                return -1; 

  

            // найти m такой, что b ^ (2 ^ m) = 1

            if (order($p, $b) == pow(2, $m)) 

                break

        

        if ($m == 0) 

            return $x

  

        // обновляем значения x, g и b

        // согласно алгоритму

        $x = ($x * pow1($g, pow(2, $r - $m - 1), $p)) % $p

        $g = pow1($g, pow(2, $r - $m), $p); 

        $b = ($b * $g) % $p

  

        if ($b == 1) 

            return $x

        $r = $m

    

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

$n = 2; 

  
// р должно быть простым

$p = 113; 

  

$x = STonelli($n, $p); 

  

if ($x == -1) 

    print("Modular square root is not exist\n"); 

else

    print("Modular square root of "

          "$n and $p is $x\n"); 

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


Выход :

Modular square root of 2 and 113 is 62

Для более подробной информации о вышеупомянутом алгоритме, пожалуйста, посетите:
http://cs.indstate.edu/~sgali1/Shanks_Tonelli.pdf

Подробнее о примере (2, 113) см.
http://www.math.vt.edu/people/brown/class_homepages/shanks_tonelli.pdf

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

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

Найти квадратный корень по модулю р | Набор 2 (алгоритм Шенкса Тонелли)

0.00 (0%) 0 votes