辗转相除在密码分析中的应用

The Application of Division Algorithm in Cryptanalysis

在高等代数和初等数论教学中,辗转相除法是确定两个多项式的最大公因式或两个整数的最大公因子的最基本的方法。主要研究如何利用此方法进行流密码分析.具体来说,将结合求解多项式的最大公因式和求解整数的最大公因子的算法,分析以国际流密码标准算法ZUC为背景而引出来的小m-序列的最低有效位序列的2-adic复杂度,以此说明辗转相除法在实际问题中的重要应用.因而为教师讲授抽象难以理解的辗转相除理论提供一个教学案例,借此来提高学生学习该理论的积极性.

In the teaching of Advanced Algebra and Elementary Number Theory,the Successive Division Algorithm(SDA) is a basic method of determining the Greatest Common Divisor(GCD) of two polynomials or two integers.In this paper,we will study on how to make an analysis of cipher using the SDA.More concretely,combining the algorithms to compute the greatest common divisors of two polynomials and two integers,we will analyze the 2-adic complexity of the least significant bit sequence of m-sequence which is derived from the International Standard of Stream Cipher Algorithm ZUC so that we can explain that the SDA has important applications in practical problems.Therefore,by such a teaching case,those teachers who teach related courses could use this method to improve the students’ learning enthusiasm of this theory.