一个改进的Euclid算法
摘要
最大公因子(GCD)计算是计算数论的基础课题之1,它在密码算法和密码分析中有着非常广泛的应用。本文主要研究正整数的GCD计算问题。
本文首先介绍了算法的相关概念和当前现有的GCD算法,然后列出了最大公因子的几个基本性质。在描述了经典Euclid算法及其扩展、2进制GCD算法及其求模逆算法并对它们分析之后,提出了1个在这些算法基础上改进而来的Euclid改进算法。它与Euclid算法相比,在计算过程中不需要处理符号,减少了要赋值的'次数。之后,用数学方法证明算法的正确性。用C语言将算法实现,并与之前列举的经典Euclid算法等几个算法比较运算时间的长短,得出结论。对非负数值运算而言,经过改进的Euclid求乘法逆算法比原来的相应算法在计算大整数乘法逆时速度要快得多,而且这个速度上的差距与运行环境的机器配置高低成反比,与所给出的大整数的规模大小成正比。文章最后将新算法实现的C语言代码列出,以供参考。
关键词:公钥密码体制;最大公因子;Euclid算法;时间复杂度。
Abstract
Greatest Common Divisor (GCD) is one of the basic subjects in computational number theory, it has a wide application in encryption and analysis of cryptography. This thesis has mainly study of the problem of GCD calculation for the positive integers.
Firstly, this thesis introduce the related concepts of the algorithm and some GCD algorithms that current existing, then list a few basic properties of Greatest Common Divisor. Describe the classic Euclid algorithm and its extended, the binary GCD algorithm and its inverse module algorithm, and analyze to them after. Based on these algorithms, we put forward a modified Euclid algorithm and its inverse module algorithm. Compared with the Euclid algorithm, it does not need to handle sign during the period of computing, reduce the times of the assignment. After this, prove it with mathematics method. Carry out the algorithm with the C language, and compare its runtime with the classic Euclid algorithm enumerated before, get a conclusion. In the cryptographic system for the nonnegative integers, the modified inverse module Euclid algorithm is faster than the original algorithm when compute the inverse of multiplication, and the difference of the speed is directly proportional to the stand or fall of running environment and is inversely proportional to the magnitude of the integer that we gave. At the end of the thesis, we list the C language code that the new algorithm carry out, and provide a reference.
Keyword:Public key Cryptography; Greatest Common Divisor (GCD); Euclid Algorithm; Time Complexity
-
浅析行动学习法对供电企业班组长培训的重要性
论文摘要:行动学习是一种团队学习的形式。针对工作中的实际问题,团队成员通过充分的交流、质疑、反思,寻找解决工作难题的切实可行的方法。班组是供电企业最基本的细胞,班组长担当了承上启下的角色,引入行动学习的方法可以彻底解决“培训无法落地”的难题,有效提升班...
-
论基于中学生英语交际学习策略指导
论文关键词:初中英语英语交际策略指导论文摘要:本文试就中学生的英语交际学习策略指导作探析,旨在通过运用正确的教学思维模式来提高学生的语言交际和表达技能,从而提高他们的综合语言运用能力。交际策略的指导,不仅是英语课程本质功能的发展必然要求,更是提高学生语...
-
小组合作学习模式应贯彻在初中英语教学的始终
小组合作学习是以学习材料为线索、以学生为主体、以活动为形式,组织学生思考,合作完成某一任务的小组学习活动。在这种学习活动中,学生始终保持一种积极的、主动的学习状态,学生之间利用英语进行理解、交际互动。这一过程的良好实施能引起学生学习兴趣,激发学生积极...
-
有效提高英语课堂教学质量之我见
随着课程改革的深入,许多先进的教育教学理念逐渐为广大教师理解并接受,新的教学方法如同四月的鲜花竞相绽放,在课堂教学中,各地各校教改的呼声一浪高过一浪,教师们也不亦乐乎地投入到教改的大潮中,方法是多样的,但目的是单一的,那就是提高教学质量,如何提高教学质量拙见...