二元域多项式基的按字求模算法

摘要

介绍了二元域多项式基及其按位(bit)求模算法,给出了一种新的通用的不要预计算的二元域多项式基按字(word)求模算法,由于可以选择不同的字长如8位字长或16位字长等,因而该算法既适合软件也适合硬件.在32位字长PC机环境下,给出了针对特定二元域和模约多项式的简化算法.在大量实验的基础上,对按字求模算法和按位求模算法的运算结果和运算速度的比较结果表明,两者运算结果相同,但前者平均运算速度比后者快30多倍.%Binary fields of polynomial basis and its bit reduction algorithm are introduced.Then a new and universal word reduction algorithm without precomputation about binary fields of polynomial basis is given.This algorithm is adapted to both software and hardware because can select different word size such as 8 or 16 bits word size.Moreover two algorithms in a simpler style are presented according to given binary fields and modular polynomials over 32 word size PC environment; on the basis of a lot of experiments done on PC, operation result and speed of word reduction algorithm are compared to bit reduction algorithm, and the conclusion is found that both operation results are identical and the average operation speed of the former is thirty more times quicker than the latter.