Rapid Large Integer Modular Arithmetic Algorithm And Implementation

Large integer modular calculations, e.g. the modular exponentiation, are the core and the most time consuming steps in public key crytographic schemes such as RAS and ElGammal schemes, in those the security is guaranteed by the assumption that the integers is large enough, say 1024 or 2048 bits long. This thesis, focused on the large integer modular computations, studies the two ways to reduce the time consumed by modular exponentiation --- algorithms for fast modular multiplication and algorithms for computing powers with the least numbers of modular multiplication. A method called Montgomery modular multiplication is the most significant way of fast modular multiplication. The Montgomery method and its improvements are studied and the performances are analyzed in this thesis. Then, by focused on the performance of variable sliding window method proposed by Knuth, a practical way to get the optimized length of sliding window is introduced. Roughly, the thesis could be divided into two parts -the algorithms analyzing for fast modular computation and the software implementation of the basic algorithms. The latter pay special attention to the software implementation environments, including the technical details such as programming interface, data structures and 32-bits Visual C++ inline assembler. A sorftware packet is designed and implemented at last, which can perform the modular multiplication with equal 2048-bits long of modulu and operands within approximately 5.239ms and the modular exponentiation with equal 2048-bits long of modulu, exponent and base within approximately 4290.559ms.