原本算法
摘抄参考文献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
春秋十二月 阅读(257)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm