模归约算法的数学基础研究

 多项式模归约算法是计算机代数中的基本问题之一,在编码算法和密码体制设计中有着广泛应用.提出了模归约算法中的2类基本算子:字归约算子、半字归约算子,并进一步证明了2类算子的计算量具有某种形式的不变量(如果满足一定的条件),从而证明了模归约算法计算量的线性性质,为其算法设计和分析提供了理论基础.还通过实例给出了2个算子在ECC和AES密码算法中的一些应用.

Research of mathematical foundation for modulo reduction algorithms

Polynomial modulo reduction algorithms are one of the fundamental issues of computer algebra,and widely used in coding algorithms and cryptographic system design.Two basic reduction operators,namely word reduction operator and semi-word reduction operator,are presented.Furthermore,it is proved that the computation time of the two operators are invariant if some conditions hold,and the computation time of the modulo reduction algorithms are of linear form.These can be the theoretical foundation for the algorithm design and analysis.Moreover,the two operators are applied to AES and ECC algorithms in some examples.