随笔-157  评论-223  文章-30  trackbacks-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] 代数学基础与有限域   林东岱
posted on 2024-09-07 23:07 春秋十二月 阅读(302) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


本博客所有随笔均为原创,因为不定期维护更新,所以转载请注明出处,如有问题和建议,请留言或评论,发表您的宝贵意见,藉此平台以分享交流、共同进步。 联系方式:微信theory-math
<2025年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

常用链接

留言簿(74)

随笔分类(156)

随笔档案(157)

文章分类(30)

关注的开源项目

最新随笔

积分与排名

  • 积分 - 410759
  • 排名 - 56

最新评论

阅读排行榜

评论排行榜