把mathe的链接发到这边 你不是推崇穷举法么？
直接列出模的平方剩余表，从中找呗。计算量也不大，至少是多项式时间的。 hujunhua 发表于 2019-3-14 10:44
你不是推崇穷举法么？
直接列出模的平方剩余表，从中找呗。计算量也不大，至少是多项式时间的。
大前提:穷举法有效的时候推荐穷举法!
穷举法没效果,还推荐啥?
给你一个一百位的大素数,你怎么计算这个二次同余方程的解? mathematica 发表于 2019-3-13 15:13
看算法数论,这本书没提到求原根!
Clear["Global`*"];(*Clear all variables*)
(*算法数论,有限域的开平方算法,附录*)
FiniteSqrt:=Module[{beta,s,t,e,h,b},
If==-1,Return];
(*找到非剩余*)
beta=2;While!=-1,beta=beta+1];
(*p-1=2^s*t*)
s=0;t=p-1;While==0,s=s+1;p=p/2];
e=0;
Do,p];
(*个人觉得这个IF下面应该增加break*)
If!=1,e=e+2^i;Break[]],
{i,1,s-1,1}
];
h=Mod,p];
b=Mod*PowerMod,p];
Return
]
FiniteSqrt
FiniteSqrt
FiniteSqrt
按照这个,我写了一个程序!
页:
1
[2]