论文部分内容阅读
求最大公因子（GCD）是计算数论中重要研究课题之一。GCD算法的实现效率对于有理数或者整数环上计算问题的解决有着重要的作用。GCD算法在密码算法实现和密码分析中有着广泛的应用，如RSA体制系统参数的生成、基于椭圆曲线的整数分解算法的核心步骤等。本文利用k-ary右移消减方法提出了快速GCD算法，并结合寻找辅助因子算法提出递归GCD算法。具体主要结果如下： 1.基于k-ary右移消减方法，在第四章提出快速GCD算法，使得每次循环平均消减约80个比特。实验结果表明：该算法比二进制GCD算法所需循环次数降低30倍左右，实现效率高。 2.本文第五章提出的寻找辅助因子算法复杂度能达到O(nlog2nloglogn)，该算法能有效处理大规模整数输入。 3.基于k-ary右移消减方法，提出了以改进辅助因子算法为核心的递归GCD算法，实验结果发现该算法对长度为n比特的整数输入，每次循环平均消减约0.2n个比特。 4.递归GCD算法的时间复杂度达到了M(n)logn。当乘法复杂度M(n)达到已有最好复杂度O(nlognloglogn)时，该算法复杂度为拟线性时间O(nlog2nloglogn)，这也是迄今为止已知的GCD算法中最好的时间复杂度。