Patent ID: 6598061
Filing Date: 2003-07-22
Classification: G06F

Abstract:
A system for performing a modular multiplication a*b*2âˆ’N modulo n, where a, b and n are N-bit integers, comprising:a multiplier for multiplying a Y-bit number by a Z-bit number; partitioning logic for partitioning the integer a into a plurality of first sections, each first section being of a size which is a multiple of Y, and for partitioning the integer b into a plurality of second sections, each second section being of a size which is a multiple of Z; a multiplication unit for applying operations to control the multiplier to perform a sequence of multiplications to multiply one of said first sections by one of said second sections in order to generate a number of output operands for use in subsequent operations performed by the multiplication unit; a controller for sequentially inputting one of said first sections and one of said second sections into the multiplication unit along with predetermined ones of said output operands from preceding operations performed by the multiplication unit, until each first section has been multiplied by each second section.