Methods and apparatus for incomplete modular arithmetic

A cryptographic system, comprising a processor that includes a word-wise, incompletely-reduced-number arithmetic module, wherein the processor includes an input configured to receive a series of s w-bit words associated with a cryptographic parameter, an output configured to deliver an incompletely reduced number based on the series of words, and memory configured to store a value of a Montgomery radix R=2sw.

A cryptographic system, comprising a processor that includes a word-wise, incompletely-reduced-number arithmetic module, wherein the word-wise, incompletely-reduced-number arithmetic module includes:

• an input configured to receive a first operand and a second operand as a first and a second series of words, respectively, wherein the first and the second operands have the same or different values;
• and
• a processor configured to execute a series of word additions between corresponding words of the first and second operands to obtain a first intermediate sum and evaluate a carry value associated with a sum of most significant words of the operands, and based on the evaluation of the carry value, add a correction factor for addition to the first intermediate sum to produce a second intermediate sum, wherein the correction factor for addition is F=2m−Ip, wherein m is a maximum number of bits in the words that represent the operands, p is a modulus, and I is a largest integer such that F is between 1 and p−1.

A cryptographic system, comprising a processor that includes a word-wise, incompletely-reduced-number arithmetic module, wherein the word-wise, incompletely-reduced-number arithmetic module includes:

• memory configured to represent a first operand and a second operand as a first and a second series of words, respectively, wherein the first and the second operands have the same or different values:
• and
• a processor configured to execute a series of word subtractions between corresponding words of the first and second operands to obtain a first intermediate difference, evaluate borrow value associated with a difference of most significant words of the operands, and add a correction factor for subtraction to the first intermediate difference based on the evaluation of the borrow value to produce a second intermediate difference, wherein the correction factor for subtraction is G=Jp−2m, wherein m is a maximum number of bits used to represent an operand, p is a modulus, and J is a smallest integer such that G is between 1 and p−1.