文件名称：基于Miller-Rabin素性检测的多项式分解算法* (2014年)
文件大小：535KB
文件格式：PDF
更新时间：2024-07-04 23:36:57
工程技术 论文
通过将Miller-Rabin素性检测的思想拓展到多项式域，随机二分搜索可应用到多项式分解中。并以此为基础，分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为1/4；第二种算法在代数数域上每次分解模素理想P的多项式的失败概率最多为1/2，当代数数域为偶数次扩展或者P|( p)满足 p为素数且4|p-1的形式时，失败概率至多为3/8。和原有算法相比较降低了失败概率。这两种算法都在分解之前进行了素性判断，这一特性可用于生成不可归约多项式。在讨论代数数域情况