Circuits and methods for multiplying large integers over a finite field

A method comprising:

• inputting a-limbs, d-limbs, r-limbs, of N-bit operands to a plurality of arithmetic circuits (202, 300), wherein:
• the a-limbs include a-limbs 0 through K - 2 of l bits and a-limb K - 1 of j bits of a first operand,
• the d-limbs include d-limbs 1 through K- 1 of l bits and d-limb 0 of j bits of the first operand, and
• the r-limbs include r-limbs 0 through K - 2 of l bits and r-limb K - 1 of j bits of a second operand;
• determining an intermediate term, Z, having z-limbs 0 through K, wherein:
• the determining includes determining by the plurality of arithmetic circuits, a respective set of intermediate z-limbs 0 through K- 1 for each r-limb i for i= 0 to K - 1,
• determining for r-limb 0, intermediate z-limbs 0 through K - 1 of set 0 as products of r-limb 0 and a-limbs 0 through K - 1;
• for each r-limb i, for i from 1 to K - 1,
• determining for each intermediate z-limb s from s=0 to i - 1 of set i, the intermediate z-limb s as a product of modulus, m, d-limb (K - i + s), and r-limb i,
• determining intermediate z-limb K - 1 of set i as a product of j low-order bits of a-limb (K - 1 - i) and r-limb i;
• determining for each intermediate z-limb sfrom s=i to K - 2 of set i, the intermediate z-limb s as a product of r-limb i and a-limb t for t=0 to K - 2 - i;
• and
• determining each z-limb as a sum of corresponding ones of the intermediate z-limbs of sets i through K - 1;
• computing by a modulo circuit (204) a value of G as (most significant M bits of Z * m) + (least significant Q bits of Z), wherein M is a number of bits by which a number of bits of Z exceeds N, and Q is equal to M + ceil (log2 m);
• increasing (212) G by m by the modulo circuit, in response to bits Q through N-1 of Z all having bit value one, and G ≥ 2Q - m;
• and
• assigning bits G bits 0 through Q - 1 to Y bits 0 through Q-1, and G bit Q to Y bit Q.