F_p上不可约与本原多项式的高效确定算法

F_p上不可约与本原多项式的高效确定算法Ξ F上不可约与本原多项式的高效确定算法p 1 2 王泽辉, 方小洵( 1 . 中山大学科学计算与计算机应用系 , 广东 广州 510275 ;) 2 . 广东

F_p上不可约与本原多项式的高效确定算法 Ξ F上不可约与本原多项式的高效确定算法p 12 王泽辉, 方小洵 (1 .中山大学科学计算与计算机应用系 ,广东 广州 510275 ; )2 .广东省科技情报研究所 ,广东 广州 510033 () 摘要 :对于一大类整数 nn 为素数乘于素数或 1的积,分别给出有限 域F上 n次多项式是不可约多项式与本 p3 )( 原多项式的一个充要条件 ,该 条件可通过 On次 F上乘法加以验证 ,易于硬件实现 。提出可约多项式一个充 分p 4) (条件 ,借此减少验证时间 ,并得到用 On次 F上乘法确定一个 n 次不可约多项式及一个 n次本原多项式的高 pn 效算法 。对于 ECC 中构造 F 上椭圆曲线 、序列密码中构造 LFSR ,有重要的应用价值 。p 关键词 :不可约 多项式 ;本原多项式 ;ECC ;序列密码 ;多项式时间复杂性 ;高效算法 () 中图分类号 :O15714 文献标识码 :A 文章编号 :052926579 20040620089204 () 设p 、q 为素数 ,F= ZΠ p= {0 ,1 ,,p 1不可约多项式的高效确定 算法 mm p- 1} 为有限域 ,F为 F的 m次扩张 。基于 Fp pp )( 的ECC 椭圆曲线公匙密码系统与基于 F的 (q 1以下研究的多项式均为 最高次项为 简称首 ECC 相比 ,优点是处理速度快 、易于硬件实现 ,但 )一的, 非首一可化为 首一多项式乘以非零常数 , 在处理多项式乘法之前必须先确定一个 F上 m次 p不影响不可约性 。F[ x ]为系数在 F上的多项式 pp 不可约多项式 ,这时一般整系数多项式不可约性