Finite field multiplier with intrinsic modular reduction
First Claim
1. A finite field multiplier with intrinsic modular reduction, comprising:
- an interface unit that translates an n bit wide data path to a m bit wide data path where n is less than m;
a finite field data unit coupled to the interface unit, the finite field data unit comprising m bit wide registers coupled to an arithmetic logic unit; and
a finite field control unit coupled to the finite field data unit, the finite field control unit comprising a microsequencer, and a finite state machine for controlling the finite field multipliers the microsequencer having a control port that accepts a signal requesting a finite field multiplication, and upon receiving the signal requesting a finite field multiplication, the microsequencer sends a start signal to the finite state machine which performs a finite field multiply operation and upon completion of the finite field multiply operation, the finite state machine sends a done signal to the microsequencer indicating completion of the finite field multiply operation, the finite state machine further coupling a finite field multiplication product to the finite field data unit.
6 Assignments
0 Petitions
Accused Products
Abstract
A finite field multiplier with intrinsic modular reduction includes an interface unit (1208) that translates an n bit wide data path to a m bit wide data path where n is less than m. Also included is a finite field data unit (1204) with m bit wide registers that is coupled to a finte field control unit (1202). The finite field control unit (1202) includes a microsequencer (1402) and a finite state machine multiplier (1404). The microsequencer (1402) controls the finite state machine multiplier (1404) which performs a finite field multiply operation with intrinsic modular reduction and presents a finite field multiplication product to the finite field data unit (1204).
-
Citations
6 Claims
-
1. A finite field multiplier with intrinsic modular reduction, comprising:
-
an interface unit that translates an n bit wide data path to a m bit wide data path where n is less than m;
a finite field data unit coupled to the interface unit, the finite field data unit comprising m bit wide registers coupled to an arithmetic logic unit; and
a finite field control unit coupled to the finite field data unit, the finite field control unit comprising a microsequencer, and a finite state machine for controlling the finite field multipliers the microsequencer having a control port that accepts a signal requesting a finite field multiplication, and upon receiving the signal requesting a finite field multiplication, the microsequencer sends a start signal to the finite state machine which performs a finite field multiply operation and upon completion of the finite field multiply operation, the finite state machine sends a done signal to the microsequencer indicating completion of the finite field multiply operation, the finite state machine further coupling a finite field multiplication product to the finite field data unit. - View Dependent Claims (2, 3, 4, 5)
a current finite field partial product is formed by multiplying each bit of B, one at a time, by all bits of A;
the current finite field partial product is added to a 1-bit shifted version of a previous finite field partial product, if any, to form an accumulated finite field partial product which is stored in C; and
when a most significant bit of the accumulated finite field partial product is 1, a modulo factor in M is subtracted from the accumulated finite field partial product stored in C to insure that the finite field multiplication product remains less than an irreducible value.
-
-
5. The finite field multiplier according to claim 4 wherein the 1-bit shifted version of a previous finite field partial product is formed by left shifting the previous finite field partial product 1-bit.
-
6. In a finite field multiplier having four m bit wide shift registers designated as B, A, M, and C, where B is a multiplier register, A is a multiplicand register, M is a modulo factor register, and C is a product register, which are used to provide a finite field multiplication when coupled to an arithmetic logic unit (ALU) for performing multiplying, adding, and subtracting, a method for computing a finite field product with intrinsic modular reduction comprising the steps of:
-
forming a current finite field partial product by multiplying each bit of B, one at a time, by all bits of A;
adding the current finite field partial product to a 1-bit shifted version of a previous finite field partial product, if any, to form an accumulated finite field partial product which is stored in C;
when a most significant bit of the accumulated finite field partial product stored in C is 1, subtracting a modulo factor in M from the accumulated finite field partial product to insure that the finite field multiplication product remains less than an irreducible value; and
repeating the forming and adding steps, and if necessary, the subtracting step, m times to complete the finite field multiplication.
-
Specification