...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial
【24h】

An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial

机译：多项式乘法的复杂性的上界模的不可约多项式的幂。

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let $mu _{q^{2}}(n,k)$ denote the minimum number of multiplications required to compute the coefficients of the product of two degree $n k - 1$ polynomials modulo the $k$ th power of an irreducible polynomial of degree $n$ over the $q^{2}$ element field $ {BBF }_{q^{2}}$. It is shown that for all odd $q$ and all $n = 1,2,ldots $, $liminf limits _{k rightarrow infty }{{ textstyle mu _{q^{2}}(n,k)}over { textstyle k n}}leq2 left (1 + {{ textstyle 1}over { textstyle {q} - 2}} right)$ . For the proof of this upper bound, we show that for an odd prime power $q$, all algebraic function fields in the Garcia–Stichtenoth tower over $ {BBF }_{q^{2}}$ have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.
机译：让 $ mu _ {q ^ {2}}（n，k）$ 表示计算所需的最小乘法数二阶 $ nk-1 $ 多项式的乘积系数，以 $ n $ 的不可约多项式的Notation =“ TeX”> $ k $ 次幂 $ q ^ {2} $ 元素字段上的 $ {BBF} _ {q ^ {2}} $ 。结果表明，对于所有奇数 $ q $ 和所有 $ n = 1,2，ldots $ ， $ liminf限制_ {k rightarrow infty} {{textstyle mu _ {q ^ {2}}（n，k）}在{文本样式kn}}上向左（1 + {{文本样式1}在{文本样式{q}-2}}上）$ 。为了证明这一上限，我们证明了对于奇数质数幂 $ q $ ， $ {BBF} _ {q ^ {2}} $ 上的Garcia–Stichtenoth塔具有各个角度的位置，并应用类似于多项式的Chudnovsky算法，用于对不可约多项式的幂进行模运算。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号