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

Research of mathematical foundation for modulo reduction algorithms

作　　者：陆正福[1] 何英[2] 杨邓奇[1] 王国栋[1] 

机构地区：[1]云南大学数学系,云南昆明650091 [2]昆明学院计算机系,云南昆明650031

出　　处：《云南大学学报（自然科学版）》2005年第4期305-309,共5页Journal of Yunnan University(Natural Sciences Edition)

基　　金：云南省自然科学基金资助项目(2002F0012M);云南大学校级科研重点资助项目(2003Z010C).

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

关 键 词：模归约算法 计算代数 模归约算子 AES ECC 

分 类 号：O157[理学—数学] TP301.6[理学—基础数学]