c++实现Tonelli–Shanks算法
算法思路：
输入：模p的一个二次剩余n，奇素数p（意味着勒让德符号L(n,p)=1）.
输出：整数R，使得R^2≡n(mod p，以下默认)
①从p-1中除去所有因子2，设p-1=q*2^S，其中q是奇数（也就是除去所有因子2的结果）。
②选择一个z，使得勒让德符号L(z,p)= -1（即，z是p的二次非剩余(pow(z, (p – 1) // 2,p)==p-1 ）
③令
c≡z^Q.
r≡n^((Q+1)/2 ),
t≡n^Q,
m=S.
④循环：
1.若t≡1，返回R，程序终止。
2.否则，找出最小的i，使得0≡1。可以重复做平方完成这一点。
3.令
b≡c^2 ^(m-i-1)，
r≡rb，
t≡tb^2，
c≡b^2，
m=i.
代码：
#include<iostream>
#include<math.h>
using namespace std;
int ksm(int a,int b,int c){
int ans = 1;
while(b){
if(b&1){
ans = (ans*a)%c;
}
a = (a*a)%c;
b >>= 1;
}
return ans;
}
int legendre(int n,int p){
return ksm(n,(p-1)/2,p);
}
int tonelli(int n,int p){
int q = p - 1;
int s = 0;
while(q % 2 == 0){
q /= 2;
s += 1;
}
if(s == 1)
return (int)ksm(n, (p + 1) / 4,p);
int flag;
for(int i=2;i<p;i++){
if(p - 1 == legendre(i, p)){
flag = i;
break;
}
}
int c = (int)ksm(flag, q,p);
int r = (int)ksm(n, (q + 1) / 2,p);
int t = (int)ksm(n, q,p);
int m = s;
int t2 = 0;
while((t - 1) % p != 0){
t2 = (t * t) % p;
int flag2;
for(int i=1;i<m;i++){
if((t2 - 1) % p == 0){
flag2 = i;
break;
}
t2 = (t2 * t2) % p;
}
int b = (int)ksm(c, 1 << (m - flag2 - 1),p);
r = (r * b) % p;
c = (b * b) % p;
t = (t * c) % p;
m = flag2;
}
return r;
}
int main(){
int n=78,p=137;
cout<<tonelli(n,p)<<endl;
}
//结果：30
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103341.html
