一种改进的大素数乘法的设计与实现

Design and Implementation of an Improved Multiplication of Large Prime Numbers

RSA算法作为应用较为广泛的非对称加密算法,经过蒙哥马利模乘等算法的优化后主要基于有限域运算中大数的加法运算和乘法运算,数位规模通常在1024位甚至更高。大数的乘法运算随着参与运算位数的增加会导致RSA算法的运行时间效率下降。随着多核处理器架构的普及,如何在多核多线程并行运算背景下提高RSA算法效率就成为解决RSA算法性能瓶颈的关键。本文通过多核并行运算背景下分析大数乘法算法从而提出一种改进的适应多核运算的大数相乘算法,依靠此算法提高RSA算法和大规模科学计算中高精度浮点数运算效率。

As a widely used asymmetric encryption algorithm, the RSA algorithm is mainly based on the addition and multiplication of large numbers in finite field operations after the optimization of Montgomery modular multiplication and other algorithms. The digital scale is usually 1024 bits or even higher. The multiplication of large numbers will lead to a decrease in the running time efficiency of the RSA algorithm as the number of bits involved in the operation increases. With the popularization of multi-core processor architecture, how to improve the efficiency of RSA algorithm in the context of multi-core and multi-thread parallel computing has become the key to solving the performance bottleneck of RSA algorithm. This paper analyzes the multiplication algorithm of large numbers in the context of multi-core parallel computing, and proposes an improved multi-core multiplication algorithm for large numbers. Relying on this algorithm, it improves the efficiency of high-precision floating-point arithmetic in RSA algorithm and large-scale scientific computing.