通用算法
先摘抄参考文献[1]中的算法流程如下
正确性分析
下面证明以上算法用到的事实结论,提炼为如下几个引理
算法构造思想
用到二次剩余知识,即一个待求平方元ɑ可以且只能表示为两个平方因子的乘积,其中一因子为任意随机选取的非平方因子β的偶数幂,
另一因子为叶子群H的一元素r,H作为陪集划分根群(有限域乘法群)得到β生成的集合即商群G/H的一个代表元系。这样一来,将开方转化为β与r的乘方运算,
迭代的过程就是为求那个具体的代表元β
e中的指数e(注意e必为偶数),从G
s-2到G
0=H,迭代结束后r被唯一确定,r的开方等于r的(t+1)/2次方(因为t是H的阶且为奇数,r
t+1=r)
例子测验
![](/images/cppblog_com/qinqing1984/prove-finitefield-squareroot-slove-example.PNG)
![](/images/cppblog_com/qinqing1984/prove-finitefield-squareroot-slove-example2.PNG)
特殊算法
当q是素数且q≡3(mod 4)时,存在更快的算法及测验如下
posted on 2024-08-30 22:22
春秋十二月 阅读(51)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm