Circuits and methods for multiplying large integers over a finite field

A method for implementing a hardware-based circuit arrangement on an integrated circuit (IC), the method comprising:

• receiving, from operand registers, a-limbs, d-limbs, r-limbs, of N-bit operands to a plurality of hardware arithmetic circuits, 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;
• generating, using a multiplier circuit of each hardware arithmetic circuit of the plurality of hardware arithmetic circuits, an intermediate term, Z, having z-limbs 0 through K, wherein:
• the determining includes determining using the multiplier circuit of each of the plurality of hardware 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 s from 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, using circuitry of a modulo circuit, a value of Gas (most significant M bits of Z*m)+(least significant Q bits of Z), wherein Mis a number of bits by which a number of bits of Z exceeds N, and Q is equal to M+ceil (log2 m);
• increasing, using the circuitry of the modulo circuit, 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, using the circuitry of the modulo circuit, bits G bits 0 through Q−1 to Y bits 0 through Q−1, and G bit Q to Y bit Q.