Research And Fast Implementation Of Large Integers Multiplication Algorithm

With the rapid development of computer technology and the Internet, the computer hasgone deep into all aspects of the industry, at the same time, information security has becomeincreasingly important, and the password technology is an important means of ensuringinformation security. RSA, ElGamal, and other public-key cryptographic algorithms are allbased on numerical algorithm on large integers, modular reduction, modular multiplication,modular exponentiation algorithm have been widely used. For performance reasons, thenumber of bits of large integers used in cryptographic algorithms is always less than2048bits.In scientific computation, especially in large-scale scientific computation, the floatingformat defined by IEEE754standard may not be able to meet the computational accuracyrequirements, large integers can be used to build high-precision floating-point data types toensure the correctness of the final output. In addition, large integers have also been used toaccurately calculate some constants, such as e and π, etc. In such applications, large integersmultiplication is the core of computation, and the amount of data is greater. Its decimal digitsmay reach one hundred million or more, sometimes referred to as huge integers.The paper focuses on the math functions, conducted in-depth study of the core of thenumerical algorithm--large integers multiplication algorithm. First, the paper brieflysummarizes mathematical knowledge on large integers multiplication algorithm, introducesthe underlying implementation and basic operation of large integers. On this basis, the papermakes comparative analysis of the tradition of the written calculation multiplication, Combamultiplication, Karatsuba multiplication and FFT multiplication, and gives the rapidimplementation, provides detailed test data. Last, the paper proposes an improvedmultiplication algorithm that combines Karatsuba multiplication and FFT multiplication. Testsshow that, it has good flexibility and high efficiency.Under32-bit Windows operating system, taking C99standard c as the developmentlanguage, with VC++2010as development tools, the papaer implements all algorithms andcarries on the optimized design, gives detailed experimental data through careful tests.