New Algorithms for Generating Conway Polynomials over Finite Fields
New Algorithms for Generating Conway Polynomials over Finite Fields
复制标题
生成有限域上康威多项式的新算法
DOI：
10.1016/j.jsc.2004.03.002
复制
发表时间：
1998
影响因子：
0.7
通讯作者：
A. L. Nicholas
中科院分区：
文献类型：
--
作者：
S. Lenwood;A. L. Nicholas
素特征为p的有限域中的算术通常使用Zp[X]中的不可约多项式。一类特殊的不可约多项式，通常称为康威多项式，提供了一种以兼容方式表示几个特征为p的有限域的方法。康威多项式用于计算代数系统，如GAP和Magma，以表示有限域。对于一个特定的有限域，康威多项式的生成以前是通过通常昂贵的蛮力搜索来完成的。我们提出了两个新的算法生成康威多项式，避免暴力搜索。我们已经实现了这些算法之一的岩浆，并提出了许多新的康威多项式产生我们的实施。
Arithmetic in a finite field of prime characteristic p normally employs an irreducible polynomial in Zp[X] . A particular class of irreducible polynomials, generally known as Conway polynomials, provides a means for representing several finite fields of characteristic p in a compatible manner. Conway polynomials are used in computational algebra systems such as GAP and Magma to represent finite fields. The generation of the Conway polynomial for a particular finite field has previously been done by an often expensive brute force search. We present two new algorithms for generating Conway polynomials that avoid the brute force search. We have implemented one of these algorithms in Magma and present numerous new Conway polynomials generated by our implementation.