许鑫，李顺东

陕西师范大学计算机科学学院，西安 710062

大整数取模的快速运算

许鑫，李顺东

陕西师范大学计算机科学学院，西安 710062

1 引言

大整数取模运算在公钥密码学中具有重要的实际应用价值，如RSA[1]算法。在进行大量的加密/解密运算时，大整数取模运算是制约RSA算法效率的主要因素，这使得RSA算法的计算复杂度较高，在与相同安全级别的对称加密算法[2]相比时，RSA算法的运算效率很低。因此，在公钥密码学中，对大整数取模算法的改进具有重要的实用价值。传统的大整数取模运算步骤主要是一个试商的过程，即每一次试商都需要做一次遍历，每次遍历中还需要做乘法和试减运算，使得时间复杂度为O(n2)，效率很低。因此提出了很多种对大整数取模运算的改进算法，如蒙哥马利（Montgomery）[3]算法和欧几里德除法[4]等，但都没有达到理想的效果。

本文另辟蹊径，依据分治法[5]思想，提出一种改进大整数取模运算的快速算法，将原来的遍历运算转换成8次大整数乘法运算和准确试商运算，使得计算复杂度降低到O(n(m-n))，极大地提高了大整数取模运算的效率，从而改进和优化RSA算法。

2 大整数取模快速算法

2.1 大整数取模算法

大整数取模运算需要进行乘法和减法两个步骤，对每一位的商都要重复这两个步骤。设有m位和n位两个大整数A和B(m＞n＞1)，取模运算表示成：

首先截取大整数A的前n位对大整数B进行试减运算，然后将大整数A的第n+1位添加至余数的末尾组成新的被除数，如此循环，直至最后的余数小于大整数B，此时的余数即是最后的结果C。……