整数及IF2上多项式的最大公因子计算

论文摘要

最大公因子（GCD）计算是计算数论的基础课题之一,它在密码算法和密码分析中有着非常广泛的应用,本文主要研究了整数及IF2上多项式的GCD计算问题。 本文首先考虑了Z上的一些基本运算,包括加减乘除、整除法、模2m逆、模2m除法、Montgomery模乘等,并针对各自特点给出了这些基本算法优化的软件实现:对于IF2[x]上的基本运算,给出了乘法和除法的优化软件实现。所有这些基本运算的算法是实现快速GCD计算的基础。 其次,介绍了整数GCD计算的经典算法—Euclid算法,扩展Euclid算法（EEA）在Euclid算法的基础上增加了对辅助因子的计算。通过对EEA的计算过程进行分析,得到了一些重要的性质。利用这些性质,本文给出了高精度数的最高位与它们自身商序列吻合的充要条件。 另外,本文给出了约简的定义,整数GCD算法中逐步减小输入整数规模的变换都可以看作约简。主要介绍了最高位优先的Lehmer类约简和最低位优先的κ-ary类约简,并主要对κ-ary类约简中的JW约简进行了优化的软件实现。为使JW约简适合扩展GCD计算,给出了M-JW约简。在分析和研究这些约简方法的基础上,结合JW约简与其它多种约简方法,给出了一个新的GCD算法。对于整数规模为512-16384比特的GCD计算,该算法相对于二进GCD算法和Lehmer GCD算法有较高的软件实现效率。作为应用,本文还考虑了GCD算法在模除和Montgomery模逆运算中的用法。 最后,把整数GCD的计算方法自然地推广到IF2上多项式的GCD计算中,对于JW约简在IF2[x]上与在Z上的不同实现方法进行了讨论,利用了互反多项式,减少了一次模x2w除法的计算,提高了IF2[x]上JW约简的实现效率。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 最大公因子的基本性质
• 1.2 前人的结果和我们的工作
• 1.3 本文章节安排
• 第二章 基本概念和一些基本运算方法
• 2.1 基本概念和符号
• 2.2 整数的一些基本运算
• 2上多项式的一些基本运算'>2.3 F₂上多项式的一些基本运算
• 2.4 小结
• 第三章 整数GCD计算
• 3.1 Euclid算法和扩展Euclid算法
• 3.2 高精度GCD计算的初步探讨
• 3.3 整数GCD计算中的约简
• 3.4 一个GCD算法
• 3.5 GCD算法的应用
• 3.6 小结
• 2上多项式的GCD计算'>第四章 F₂上多项式的GCD计算
• 第五章 结束语
• 致谢
• 参考文献