IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    不可约多项式判别算法的改正

    春秋十二月发表于 2024-09-07 15:07:00
    love 0
    原本算法
        摘抄参考文献1中附录的算法流程如下
        

    例子测验
       
        

    改正后的算法
           改正之前,先理清原本算法判别不可约多项式所用的原理。其原理是若f(x)可约,当且仅当存在次数i<=d=[deg(f(x))/2]的不可约因子g(x),而此时gcd(xq^i-x, f(x))≠1。
       根据参考文献2(详见如下定理),xq^i-x是所有i次不可约多项式的乘积,因此它必定包含g(x)而与f(x)存在公因子。不可约判别算法的思想应该是遍历次数1到d的所有不可约多项式
     (没必要检测大于d的不可约多项式,因为若f(x)可约则其分解因子中必定存在不大于d的不可约多项式),检测输入多项式与它们是否存在公因子。所以这个原理是正确的,只是实现不对,
       略作改正如下(类c语言描述)
       

    重新测验
       

       


    参考文献
       [1] 算法数论                 裴定一、祝跃飞
       [2] 代数学基础与有限域   林东岱


    春秋十二月 2024-09-07 23:07 发表评论


沪ICP备19023445号-2号
友情链接