原本算法
摘抄參考文獻1中附錄的算法流程如下
例子測驗
改正后的算法
改正之前，先理清原本算法判別不可約多項式所用的原理。其原理是若f(x)可約，當且僅當存在次數i<=d=[deg(f(x))/2]的不可約因子g(x)，而此時gcd(x
q^i-x, f(x))≠1。
根據
參考文獻2（詳見如下定理），x
q^i-x是所有i次不可約多項式的乘積，因此它必定包含g(x)而與f(x)存在公因子。不可約判別算法的思想應該是遍歷次數1到d的所有不可約多項式
（沒必要檢測大于d的不可約多項式，因為若f(x)可約則其分解因子中必定存在不大于d的不可約多項式），檢測輸入多項式與它們是否存在公因子。所以這個原理是正確的，只是實現不對，
略作改正如下（類c語言描述）
重新測驗
參考文獻
[1] 算法數論 裴定一、祝躍飛
[2] 代數學基礎與有限域 林東岱
posted on 2024-09-07 23:07
春秋十二月 閱讀(393)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm