Abstract: To optimize the modular multiplication of large integer，based on the idea of winning time at the cost of space.A novel run-length coding method is proposed by modifying sliding window coding.And then a fast modular multiplication algorithm is designed，and its time complexity and space complexity are analyzed.Finally，the algorithm’s efficiency is compared to which based on the optimal sliding window coding.The newly designed algorithm greatly exceed the latter one in the time complexity while remain the same level in the space complexity.Tested under the same environment，the former algorithm’s efficiency increases 41%.

Key words: public-key cryptosystem, modular multiplication, sliding window coding, run-length coding

摘要： 为了优化提高大整数模乘的运算效率，基于以空间换时间的思想，在改进滑动窗口编码的基础上，提出了一种新颖的游程编码，并在此基础上，设计了一种快速大数模乘的实现算法，分析了该算法的时间复杂度和空间复杂度。分析结果表明，与基于最佳滑动窗口编码的大数模乘算法相比，所设计的算法在保持空间复杂度数量级的同时，时间效率上得到了很大的提高。在同等硬件软件环境下测试，新算法平均运算速度比前者约提高41%。此外，新算法的预处理过程也更加简单。

关键词: 公钥密码, 大数模乘, 滑动窗口编码, 游程编码