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

The Application of Division Algorithm in Cryptanalysis

作　　者：孙玉花 闫统江 张景明 SUN Yu-hua;YAN Tong-jiang;ZHANG Jing-ming(College of Science,China University of Petroleum,Qingdao 266580,China)

机构地区：[1]中国石油大学(华东)理学院,山东青岛266580

出　　处：《数学的实践与认识》2020年第21期286-290,共5页Mathematics in Practice and Theory

基　　金：中国石油大学(华东)教改项目“与理科专业教育深度融合多元协同构建双创教育生态链的探索与实践”(JY-A201803);国家自然科学基金青年基金(61902429);中央高校基本科研业务费专项资金(19CX02058A)。

摘　　要：在高等代数和初等数论教学中,辗转相除法是确定两个多项式的最大公因式或两个整数的最大公因子的最基本的方法。主要研究如何利用此方法进行流密码分析.具体来说,将结合求解多项式的最大公因式和求解整数的最大公因子的算法,分析以国际流密码标准算法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.

关 键 词：辗转相除 流密码 小m-序列 比特分位序列 2-adic复杂度 

分 类 号：G642[文化科学—高等教育学] O15-4[文化科学—教育学] O156.1-4[理学—数学]