Fast modular multiplication of large integers

A computer system comprising:

• a processor set;
• one or more computer-readable storage media;
• and
• program instructions stored on the one or more computer-readable storage media to cause the processor set to perform operations comprising:
• performing elliptic curve cryptography (ECC) operations for an approach to public-key cryptography based on algebraic structure of elliptic curves over finite fields by combining a key agreement with a symmetric encryption scheme, the ECC operations comprising:
• receiving a plurality of first operand values, wherein:
• the plurality of first operand values are integer values;
• and
• the plurality of first operand values originate from a Solinas reduction operation;
• adding, by a hardware n-way binary adder comprising a carry sum adder and a binary adder, using binary addition, the plurality of first operand values, resulting in a sum value, wherein:
• the carry sum adder receives the plurality of first operand values and outputs, to the binary adder, a carry/sum vector pair represented in a redundant number form;
• and
• the redundant number form is a reduced-radix form;
• determining a single combined modular correction term for a binary sum of all operand values based on:
• (i) leading bits of the sum value and (ii) by using a lookup table that gives a modulus number represented by the leading bits of the sum value;
• and
• performing, by a hardware modular adder comprising a second hardware binary adder and a multiplexer, a modular addition of the sum value and the single combined modular correction term, resulting in a modular sum of the plurality of first operand values.

A computer program product comprising:

• one or more computer-readable storage media;
• and
• program instructions stored on the one or more computer-readable storage media to perform operations comprising:
• performing elliptic curve cryptography (ECC) operations for an approach to public-key cryptography based on algebraic structure of elliptic curves over finite fields by combining a key agreement with a symmetric encryption scheme, the ECC operations comprising:
• receiving a plurality of first operand values, wherein:
• the plurality of first operand values are integer values;
• and
• the plurality of first operand values originate from a Solinas reduction operation;
• adding, by a hardware n-way binary adder comprising a carry sum adder and a binary adder, using binary addition, the plurality of first operand values, resulting in a sum value, wherein:
• the carry sum adder receives the plurality of first operand values and outputs, to the binary adder, a carry/sum vector pair represented in a redundant number form;
• and
• the redundant number form is a reduced-radix form;
• determining a single combined modular correction term for a binary sum of all operand values based on:
• (i) leading bits of the sum value and (ii) by using a lookup table that gives a modulus number represented by the leading bits of the sum value;
• and
• performing, by a hardware modular adder comprising a second hardware binary adder and a multiplexer, a modular addition of the sum value and the single combined modular correction term, resulting in a modular sum of the plurality of first operand values.