通用算法
先摘抄参考文献[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）
例子测验
特殊算法
当q是素数且q≡3(mod 4)时，存在更快的算法及测验如下
posted on 2024-08-30 22:22
春秋十二月 阅读(51)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm