...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Finite fields and their applications >On the enumeration of irreducible polynomials over GF(q) with prescribed coefficients
【24h】

On the enumeration of irreducible polynomials over GF(q) with prescribed coefficients

机译：具有规定系数的GF（q）上不可约多项式的枚举

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present an efficient deterministic algorithm which outputs exact expressions in terms of n for the number of monic degree n irreducible polynomials over IF, of characteristic p for which the first l p coefficients are prescribed, provided that n is coprime to p. Each of these counts is l(q(n-1)+O(q(n/2))). The main idea behind the algorithm is to associate to an equivalent problem a set of Artin-Schreier curves defined over F-q whose number of F(q)n-rational affine points must be combined. This is accomplished by computing their zeta functions using a p-adic algorithm due to Lauder and Wan. Using the computational algebra system Magma one can, for example, compute the zeta functions of the arising curves for q = 5 and l = 4 very efficiently, and we detail a proof-of-concept demonstration. Due to the failure of Newton's identities in positive characteristic, the l = p cases are seemingly harder. Nevertheless, we use an analogous algorithm to compute example curves for q = 2 and l = 7, and for q = 3 and l = 3. Again using Magma, for q = 2 we computed the relevant zeta functions for l = 4 and l = 5, obtaining explicit formulae for these open problems for n odd, as well as for subsets of these problems for all n, while for q = 3 we obtained explicit formulae for l = 3 and n coprime to 3. We also discuss some of the computational chal- lenges and theoretical questions arising from this approach in the general case and propose some natural open problems. (C) 2019 Elsevier Inc. All rights reserved.
机译：我们提出了一种有效的确定性算法，该算法针对IF上的单调数n个不可约多项式的数量，以n的形式输出精确表达式，其特征p为p的第一个l 系数，条件是n是p的互质数。这些计数中的每一个都是l / n（q（n-1）+ O（q（n / 2）））。该算法的主要思想是将与F-q上定义的一组Artin-Schreier曲线相关的等效问题相关联，该曲线必须组合F（q）n有理仿射点的数量。这是由于Lauder和Wan通过使用p-adic算法计算其zeta函数来完成的。例如，使用计算代数系统Magma可以非常高效地计算q = 5和l = 4时出现的曲线的zeta函数，并且我们详细介绍了概念证明。由于牛顿身份在正特性上的失败，l> = p的情况似乎更加困难。尽管如此，我们还是使用类似的算法来计算q = 2和l <= 7以及q = 3和l = 3的示例曲线。再次使用岩浆，对于q = 2我们计算了l = 4和l = 5，获得针对n个奇数的所有这些开放问题以及所有n的这些问题的子集的显式，而对于q = 3，我们获得针对l = 3的显式和n互质数为3。这种方法在一般情况下产生的计算挑战和理论问题，并提出了一些自然的开放性问题。 （C）2019 Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号