基于Miller-Rabin素性检测的多项式分解算法

• 作者: 孙荣辛 田园
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 概率性算法 多项式分解 Miller-Rabin素性检测 有限域 代数数域
• 年，卷（期）: 2014,（12）
• 所属期刊栏目: 网络与信息安全
• 页码范围: 1474-1484
• 页数: 11页
• 分类号: TP309
• 字数: 11231字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1406002

摘要

通过将Miller-Rabin素性检测的思想拓展到多项式域，随机二分搜索可应用到多项式分解中。并以此为基础，分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为1/4；第二种算法在代数数域上每次分解模素理想P的多项式的失败概率最多为1/2，当代数数域为偶数次扩展或者P|( p)满足 p为素数且4|p-1的形式时，失败概率至多为3/8。和原有算法相比较降低了失败概率。这两种算法都在分解之前进行了素性判断，这一特性可用于生成不可归约多项式。在讨论代数数域情况时，给出了完整的多项式运算的时间复杂证明，弥补了代数数域内多项式计算理论模型上的空白。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	田园	大连理工大学国家示范性软件学院	15	74	5.0	8.0
2	孙荣辛	大连理工大学国家示范性软件学院	3	5	1.0	2.0