同余方程x^2=a(mod p)如何求解

mathematica

https://en.m.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

把mathe的链接发到这边

hujunhua

你不是推崇穷举法么？
直接列出模的平方剩余表，从中找呗。计算量也不大，至少是多项式时间的。

mathematica

hujunhua 发表于 2019-3-14 10:44
你不是推崇穷举法么？
直接列出模的平方剩余表，从中找呗。计算量也不大，至少是多项式时间的。

大前提:穷举法有效的时候推荐穷举法!
穷举法没效果,还推荐啥?
给你一个一百位的大素数,你怎么计算这个二次同余方程的解?

mathematica

mathematica 发表于 2019-3-13 15:13
看算法数论,这本书没提到求原根!

1. Clear["Global`*"];(*Clear all variables*)
   
2. (*算法数论,有限域的开平方算法,附录*)
   
3. FiniteSqrt[a_,p_]:=Module[{beta,s,t,e,h,b},
   
4.     If[JacobiSymbol[a,p]==-1,Return[False]];
   
5.     (*找到非剩余*)
   
6.     beta=2;While[JacobiSymbol[beta,p]!=-1,beta=beta+1];
   
7.     (*p-1=2^s*t*)
   
8.     s=0;t=p-1;While[Mod[p,2]==0,s=s+1;p=p/2];
   
9.     e=0;
   
10.     Do[h=Mod[a*PowerMod[beta,-e,p],p];
    
11.         (*个人觉得这个IF下面应该增加break*)
    
12.         If[PowerMod[h,2^(s-i-1)*t,p]!=1,e=e+2^i;Break[]],
    
13.         {i,1,s-1,1}
    
14.     ];
    
15.     h=Mod[a*PowerMod[beta,-e,p],p];
    
16.     b=Mod[PowerMod[beta,e/2,p]*PowerMod[h,(t+1)/2,p],p];
    
17.     Return[b]
    
18. ]
    
19. 
    
20. FiniteSqrt[2,97]
    
21. FiniteSqrt[3,13]
    
22. FiniteSqrt[5,29]
    

复制代码

按照这个,我写了一个程序!