Implementation Of Modular Multiplication Over Fp

Public key cryptosystems have been widely applied in information security filed. There are two different popular public key cryptosystems: RSA system based on Integer Factor Problem and Elliptic curve cryptosystem based on Discrete Logarithms Problem of elliptic curve.Modular multiplication is the foundation arithmetic operation of the two type public key cryptosystems, which consumes most time and resource of software and hardware. The efficiencies of modular multiplication decide the efficiencies of public key cryptosystems to a great extent.To design some efficient modular multiplication algorithms has now been one of focus of research and study of application field.Multiplication and estimate of quotient are the cores of modular multiplication. According to different methods of multiplication and estimate of quotient, methods of multiplication can be classified as three type: estimate of quotient as whole, estimate of quotient step by step and Montgomery modular multiplication.This paper discusses these methods in detail and analyses the advantages and defaults of them. According to different software and hardware environment, many improved methods and advice are given. The application of the new improved methods to the implementation of public key cryptosystems usually increases efficiency.