计算机工程 ›› 2010, Vol. 36 ›› Issue (06): 140-141.doi: 10.3969/j.issn.1000-3428.2010.06.047

• 安全技术 • 上一篇    下一篇

GF(2m)上的快速模约减算法

段 斌,马自堂   

  1. (解放军信息工程大学电子技术学院,郑州 450004)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-03-20 发布日期:2010-03-20

Fast Module Reduction Algorithm over GF(2m)

DUAN Bin, MA Zi-tang   

  1. (Institute of Electronic Technology, PLA Information Engineering University, Zhengzhou 450004)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-03-20 Published:2010-03-20

摘要: 针对GF(2m)上的模约减运算问题,在基于固定三(或五)项式(FTOP)算法的基础上提出一种改进的快速算法。该算法采用动态计算分组字序号和偏移量的方法,克服FTOP只适用于特定约减多项式的不足。实验结果表明,当约减多项式项数小于123(m<719)时,该算法速度比一次一位的算法有较大提高,最大为89%,平均为30%左右,当约减多项式为任意三(或五)项式时,能达到与FTOP相同的速度。

关键词: 有限域, 模约减, 约减多项式, 快速算法

Abstract: Aiming at the problem of the module reduction operation, this paper proposes a fast algorithm based on Fixed Trinomial Or Pentanomial(FTOP) algorithm over GF(2m). By dynamically counting the index and offset of grouping words, the proposed algorithm overcomes the disadvantage of FTOP that of only available for fixed reduction polynomial, the proposed algorithm is faster than the one-time-one-bit algorithm when reduction polynomial has less terms of 123(m<719), maximum 89%, average about 30%, and with arbitrary trinomial or petanomial, it has the same speed as the FTOP’s.

Key words: finite field, module reduction, reduction polynomial, fast algorithm

中图分类号: