通用算法
先摘抄參考文獻[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-1后得到s=1，那么就沒必要選取非平方元β了（這時令β=1），直接跳到第6步得到結果。僅當s≠1才隨機選取β。這樣改進后可加快算法運行
例子測驗
特殊算法
當q是素數且q≡3(mod 4)時，存在更快的算法及測驗如下
posted on 2024-08-30 22:22
春秋十二月 閱讀(473)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm