A faster modular multiplication algorithm

Abstract

This paper describes a method for quickly computing AB mod N where N is odd. It is shown to have significant advantages over other algorithms which make it suitable for use in hardware for public key encryption. Such hardware could run at approximately twice the speed of the best currently available.

Keywords:

• Modular multiplication
• fast computer arithmetic
• digital arithmetic
• integer division
• parallel bit operations
• redundant number systems
• public key cryptography
• RSA algorithm

C.R. Categories:

• 1980 Mathematics Subject Classification (1985 Revision). Primary 11-04
• Secondary 68Q35