Finite field multiplier with intrinsic modular reduction

• US 6,230,179 B1
• Filed: 12/24/1997
• Issued: 05/08/2001
• Est. Priority Date: 04/18/1997
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited), Motorola Solutions, Inc.
• Original Assignee: Certicom Corporation (Blackberry Limited), Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Vanstone, Scott Alexander, Lambert, Robert John, Vadekar, Ashok, Dworkin, James Douglas, Glaser, P. Michael, Torla, Michael John
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/997,960
• Time in Patent Office: 1,231 Days
• Field of Search: 708/491-492, 708/625
• US Class Current: 708/492
• CPC Class Codes: G06F 2207/382 Reconfigurable for different fixed word lengths multigauge devices G06F2207/3828
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: G06F 7/722 Modular multiplication G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

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).

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.

2. The finite field multiplier according to claim 1 wherein m is 256 and n is 32.

3. The finite field multiplier according to claim 1 wherein the finite field data unit comprises four m bit wide registers coupled to the interface unit and to the finite field control unit.

4. The finite field multiplier according to claim 3 wherein the four m bit wide registers are 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 the arithmetic logic unit (ALU for performing multiplying. adding. and subtracting. with the finite state machine operating to multiply B by A by repeating the following procedure m times:

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.