求模 p |集合 2 下的平方根(Shanks Tonelli 算法)
原文:https://www . geesforgeks . org/find-平方根-模-p-set-2-shanks-tonelli-algorithm/
给定一个数“n”和一个素数“p”，求模 p 下 n 的平方根，如果它存在的话。 例:
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
我们已经讨论了欧拉准则来检查平方根是否存在。我们还讨论了一个只有当 p 是 4*i + 3 形式时才起作用的解决方案。在这篇文章中，讨论了适用于所有类型输入的 Shank Tonelli 算法。 使用 shank Tonelli 算法求模平方根的算法步骤: 1)计算 n ^((p–1)/2)(mod p)，它必须是 1 或 p-1，如果是 p-1，那么模平方根是不可能的。 2)然后，对于某些整数 s 和 e，在将 p-1 写成(s * 2^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++ program to implement Shanks Tonelli algorithm for
// finding Modular Square Roots
#include <bits/stdc++.h>
using namespace std;
// utility function to find pow(base, exponent) % modulus
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;
}
// utility function to find gcd
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Returns k such that 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;
}
// Initializing k with first odd prime number
int k = 3;
while (1)
{
if (pow(b, k, p) == 1)
return k;
k++;
}
}
// function return p - 1 (= x argument) as x * 2^e,
// where x will be odd sending e as reference because
// updation is needed in actual e
int convertx2e(int x, int& e)
{
e = 0;
while (x % 2 == 0)
{
x /= 2;
e++;
}
return x;
}
// Main function for finding the modular square root
int STonelli(int n, int p)
{
// a and p should be coprime for finding the modular
// square root
if (gcd(n, p) != 1)
{
printf("a and p are not coprime\n");
return -1;
}
// If below expression return (p - 1) then modular
// square root is not possible
if (pow(n, (p - 1) / 2, p) == (p - 1))
{
printf("no sqrt possible\n");
return -1;
}
// expressing p - 1, in terms of s * 2^e, where s
// is odd number
int s, e;
s = convertx2e(p - 1, e);
// finding smallest q such that q ^ ((p - 1) / 2)
// (mod p) = p - 1
int q;
for (q = 2; ; q++)
{
// q - 1 is in place of (-1 % p)
if (pow(q, (p - 1) / 2, p) == (p - 1))
break;
}
// Initializing variable x, b and g
int x = pow(n, (s + 1) / 2, p);
int b = pow(n, s, p);
int g = pow(q, s, p);
int r = e;
// keep looping until b become 1 or m becomes 0
while (1)
{
int m;
for (m = 0; m < r; m++)
{
if (order(p, b) == -1)
return -1;
// finding m such that b^ (2^m) = 1
if (order(p, b) == pow(2, m))
break;
}
if (m == 0)
return x;
// updating value of x, g and b according to
// algorithm
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;
}
}
// driver program to test above function
int main()
{
int n = 2;
// p should be prime
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 语言(一种计算机语言，尤用于创建网站)
// Java program to implement Shanks
// Tonelli algorithm for finding
// Modular Square Roots
class GFG
{
static int z = 0;
// utility function to find
// pow(base, exponent) % modulus
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;
}
// utility function to find gcd
static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Returns k such that 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;
}
// Initializing k with first
// odd prime number
int k = 3;
while (true)
{
if (pow1(b, k, p) == 1)
return k;
k++;
}
}
// function return p - 1 (= x argument)
// as x * 2^e, where x will be odd
// sending e as reference because
// updation is needed in actual e
static int convertx2e(int x)
{
z = 0;
while (x % 2 == 0)
{
x /= 2;
z++;
}
return x;
}
// Main function for finding
// the modular square root
static int STonelli(int n, int p)
{
// a and p should be coprime for
// finding the modular square root
if (gcd(n, p) != 1)
{
System.out.println("a and p are not coprime");
return -1;
}
// If below expression return (p - 1) then modular
// square root is not possible
if (pow1(n, (p - 1) / 2, p) == (p - 1))
{
System.out.println("no sqrt possible");
return -1;
}
// expressing p - 1, in terms of
// s * 2^e, where s is odd number
int s, e;
s = convertx2e(p - 1);
e = z;
// finding smallest q such that q ^ ((p - 1) / 2)
// (mod p) = p - 1
int q;
for (q = 2; ; q++)
{
// q - 1 is in place of (-1 % p)
if (pow1(q, (p - 1) / 2, p) == (p - 1))
break;
}
// Initializing variable x, b and g
int x = pow1(n, (s + 1) / 2, p);
int b = pow1(n, s, p);
int g = pow1(q, s, p);
int r = e;
// keep looping until b
// become 1 or m becomes 0
while (true)
{
int m;
for (m = 0; m < r; m++)
{
if (order(p, b) == -1)
return -1;
// finding m such that b^ (2^m) = 1
if (order(p, b) == Math.pow(2, m))
break;
}
if (m == 0)
return x;
// updating value of x, g and b
// according to algorithm
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;
}
}
// Driver code
public static void main (String[] args)
{
int n = 2;
// p should be prime
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");
}
}
// This code is contributed by mits
Python 3
# Python3 program to implement Shanks Tonelli
# algorithm for finding Modular Square Roots
# utility function to find pow(base,
# exponent) % modulus
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;
# utility function to find gcd
def gcd(a, b):
if (b == 0):
return a;
else:
return gcd(b, a % b);
# Returns k such that 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;
# Initializing k with first
# odd prime number
k = 3;
while (True):
if (pow1(b, k, p) == 1):
return k;
k += 1;
# function return p - 1 (= x argument) as
# x * 2^e, where x will be odd sending e
# as reference because updation is needed
# in actual e
def convertx2e(x):
z = 0;
while (x % 2 == 0):
x = x / 2;
z += 1;
return [x, z];
# Main function for finding the
# modular square root
def STonelli(n, p):
# a and p should be coprime for
# finding the modular square root
if (gcd(n, p) != 1):
print("a and p are not coprime\n");
return -1;
# If below expression return (p - 1) then
# modular square root is not possible
if (pow1(n, (p - 1) / 2, p) == (p - 1)):
print("no sqrt possible\n");
return -1;
# expressing p - 1, in terms of s * 2^e,
# where s is odd number
ar = convertx2e(p - 1);
s = ar[0];
e = ar[1];
# finding smallest q such that
# q ^ ((p - 1) / 2) (mod p) = p - 1
q = 2;
while (True):
# q - 1 is in place of (-1 % p)
if (pow1(q, (p - 1) / 2, p) == (p - 1)):
break;
q += 1;
# Initializing variable x, b and g
x = pow1(n, (s + 1) / 2, p);
b = pow1(n, s, p);
g = pow1(q, s, p);
r = e;
# keep looping until b become
# 1 or m becomes 0
while (True):
m = 0;
while (m < r):
if (order(p, b) == -1):
return -1;
# finding m such that b^ (2^m) = 1
if (order(p, b) == pow(2, m)):
break;
m += 1;
if (m == 0):
return x;
# updating value of x, g and b
# according to algorithm
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;
# Driver Code
n = 2;
# p should be prime
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);
# This code is contributed by mits
C
// C# program to implement Shanks
// Tonelli algorithm for finding
// Modular Square Roots
using System;
class GFG
{
static int z=0;
// utility function to find
// pow(base, exponent) % modulus
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;
}
// utility function to find gcd
static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Returns k such that 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;
}
// Initializing k with
// first odd prime number
int k = 3;
while (true)
{
if (pow1(b, k, p) == 1)
return k;
k++;
}
}
// function return p - 1 (= x argument)
// as x * 2^e, where x will be odd sending
// e as reference because updation is
// needed in actual e
static int convertx2e(int x)
{
z = 0;
while (x % 2 == 0)
{
x /= 2;
z++;
}
return x;
}
// Main function for finding
// the modular square root
static int STonelli(int n, int p)
{
// a and p should be coprime for
// finding the modular square root
if (gcd(n, p) != 1)
{
Console.WriteLine("a and p are not coprime");
return -1;
}
// If below expression return (p - 1) then
// modular square root is not possible
if (pow1(n, (p - 1) / 2, p) == (p - 1))
{
Console.WriteLine("no sqrt possible");
return -1;
}
// expressing p - 1, in terms of s * 2^e,
// where s is odd number
int s, e;
s = convertx2e(p - 1);
e=z;
// finding smallest q such that q ^ ((p - 1) / 2)
// (mod p) = p - 1
int q;
for (q = 2; ; q++)
{
// q - 1 is in place of (-1 % p)
if (pow1(q, (p - 1) / 2, p) == (p - 1))
break;
}
// Initializing variable x, b and g
int x = pow1(n, (s + 1) / 2, p);
int b = pow1(n, s, p);
int g = pow1(q, s, p);
int r = e;
// keep looping until b become
// 1 or m becomes 0
while (true)
{
int m;
for (m = 0; m < r; m++)
{
if (order(p, b) == -1)
return -1;
// finding m such that b^ (2^m) = 1
if (order(p, b) == Math.Pow(2, m))
break;
}
if (m == 0)
return x;
// updating value of x, g and b
// according to algorithm
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;
}
}
// Driver code
static void Main()
{
int n = 2;
// p should be prime
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);
}
}
// This code is contributed by mits
服务器端编程语言（Professional Hypertext Preprocessor 的缩写）
<?php
// PHP program to implement Shanks Tonelli
// algorithm for finding Modular Square Roots
// utility function to find pow(base,
// exponent) % modulus
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;
}
// utility function to find gcd
function gcd($a, $b)
{
if ($b == 0)
return $a;
else
return gcd($b, $a % $b);
}
// Returns k such that 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;
}
// Initializing k with first
// odd prime number
$k = 3;
while (1)
{
if (pow1($b, $k, $p) == 1)
return $k;
$k++;
}
}
// function return p - 1 (= x argument) as
// x * 2^e, where x will be odd sending e
// as reference because updation is needed
// in actual e
function convertx2e($x, &$e)
{
$e = 0;
while ($x % 2 == 0)
{
$x = (int)($x / 2);
$e++;
}
return $x;
}
// Main function for finding the
// modular square root
function STonelli($n, $p)
{
// a and p should be coprime for
// finding the modular square root
if (gcd($n, $p) != 1)
{
print("a and p are not coprime\n");
return -1;
}
// If below expression return (p - 1) then
// modular square root is not possible
if (pow1($n, ($p - 1) / 2, $p) == ($p - 1))
{
printf("no sqrt possible\n");
return -1;
}
// expressing p - 1, in terms of s * 2^e,
// where s is odd number
$e = 0;
$s = convertx2e($p - 1, $e);
// finding smallest q such that
// q ^ ((p - 1) / 2) (mod p) = p - 1
$q = 2;
for (; ; $q++)
{
// q - 1 is in place of (-1 % p)
if (pow1($q, ($p - 1) / 2, $p) == ($p - 1))
break;
}
// Initializing variable x, b and g
$x = pow1($n, ($s + 1) / 2, $p);
$b = pow1($n, $s, $p);
$g = pow1($q, $s, $p);
$r = $e;
// keep looping until b become
// 1 or m becomes 0
while (1)
{
$m = 0;
for (; $m < $r; $m++)
{
if (order($p, $b) == -1)
return -1;
// finding m such that b^ (2^m) = 1
if (order($p, $b) == pow(2, $m))
break;
}
if ($m == 0)
return $x;
// updating value of x, g and b
// according to algorithm
$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;
}
}
// Driver Code
$n = 2;
// p should be prime
$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");
// This code is contributed by mits
?>
java 描述语言
<script>
// JavaScript program to implement Shanks
// Tonelli algorithm for finding
// Modular Square Roots
let z = 0;
// utility function to find
// pow(base, exponent) % modulus
function pow1(base1,
exponent, modulus)
{
let 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;
}
// utility function to find gcd
function gcd(a, b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Returns k such that b^k = 1 (mod p)
function order(p, b)
{
if (gcd(p, b) != 1)
{
document.write("p and b are" +
"not co-prime." + "<br/>");
return -1;
}
// Initializing k with first
// odd prime number
let k = 3;
while (true)
{
if (pow1(b, k, p) == 1)
return k;
k++;
}
}
// function return p - 1 (= x argument)
// as x * 2^e, where x will be odd
// sending e as reference because
// updation is needed in actual e
function convertx2e(x)
{
z = 0;
while (x % 2 == 0)
{
x /= 2;
z++;
}
return x;
}
// Main function for finding
// the modular square root
function STonelli(n, p)
{
// a and p should be coprime for
// finding the modular square root
if (gcd(n, p) != 1)
{
System.out.prletln("a and p are not coprime");
return -1;
}
// If below expression return (p - 1) then modular
// square root is not possible
if (pow1(n, (p - 1) / 2, p) == (p - 1))
{
document.write("no sqrt possible" + "<br/>");
return -1;
}
// expressing p - 1, in terms of
// s * 2^e, where s is odd number
let s, e;
s = convertx2e(p - 1);
e = z;
// finding smallest q such that q ^ ((p - 1) / 2)
// (mod p) = p - 1
let q;
for (q = 2; ; q++)
{
// q - 1 is in place of (-1 % p)
if (pow1(q, (p - 1) / 2, p) == (p - 1))
break;
}
// Initializing variable x, b and g
let x = pow1(n, (s + 1) / 2, p);
let b = pow1(n, s, p);
let g = pow1(q, s, p);
let r = e;
// keep looping until b
// become 1 or m becomes 0
while (true)
{
let m;
for (m = 0; m < r; m++)
{
if (order(p, b) == -1)
return -1;
// finding m such that b^ (2^m) = 1
if (order(p, b) == Math.pow(2, m))
break;
}
if (m == 0)
return x;
// updating value of x, g and b
// according to algorithm
x = (x * pow1(g, Math.pow(2,
r - m - 1), p)) % p;
g = pow1(g, Math.pow(2, r - m), p);
b = (b * g) % p;
if (b == 1)
return x;
r = m;
}
}
// Driver Code
let n = 2;
// p should be prime
let p = 113;
let x = STonelli(n, p);
if (x == -1)
document.write("Modular square" +
"root is not exist\n");
else
document.write("Modular square root of " +
n + " and " + p + " is " +
x + "\n");
</script>
输出:
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 _ home page/shanks _ tonelli . pdf 本文由 Utkarsh Trivedi 供稿。如果发现有不正确的地方，请写评论，或者想分享更多关于以上讨论话题的信息
版权属于：月萌API www.moonapi.com，转载请注明出处
