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