Method and apparatus for finite field multiplication

• US 6,049,815 A
• Filed: 12/24/1997
• Issued: 04/11/2000
• Est. Priority Date: 12/30/1996
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Lambert, Robert J., Vadekar, Ashok
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/997,673
• Time in Patent Office: 839 Days
• Field of Search: 708/492, 708/491, 380/28
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A method of computing the product D of two finite field elements B and C modulo an irreducible polynomial f₁ (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F₂.spsb.n and the irreducible polynomial f₁ (x) being of degree n, which comprises the steps of representing the element B as a vector of binary digits b_i, where b_i is a co-efficient of an i^th basis element of the ONB representation of element B, in polynomial order, representing the element C as a vector of binary digits c_i, where c_i is a co-efficient of an i^th basis element of the ONB representation of element C, arranged in polynomial order, initializing a register A, selecting a digit c_i of the vector C, computing a partial product vector A of the i^th digit c_i of the element C and the vector B, adding the partial product to the register A, shifting the register A, reducing the partial product A by a multiple f₂ (x) of the irreducible polynomial f₁ (x) if bits in a position above n are set, storing the reduced partial product in the register A, repeating for each successive bit of the vector C and upon completion the register A containing a final product vector; and reducing the final product vector A by the irreducible polynomial f₁ (x) if an n^th bit of the register is set. The reduction step by the multiple of the irreducible polynomial simply involves a shift operation performed on the partial products.

Claims

1. A computer system for determining the product of two finite field elements B and C modulo an irreducible polynomial f₁ (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F₂.spsb.n and said irreducible polynomial f₁ (x) being of degree n, comprising:

(a) a memory containing a first vector of binary digits b_i, where b_i is a co-efficient of the i^th basis element of said ONB representation of element B, arranged in polynomial order;

a second vector of binary digits c_i, where c_i is a co-efficient the i^th basis element of said ONB representation of element C, arranged in polynomial order;

a computer program having functions for invocation, said functions for computing a partial product of a multiplier with a multiplicand and for reducing said partial product by a multiple of said irreducible polynomials f₁ (x);

(b) a control program for invoking said functions; and

(c) a processor for running said computer program.

2. A method of determining the product of two finite field elements B and C modulo an irreducible polynomial f₁ (x) in a computer system having a computer program with functions for invocation and a control program for invoking said functions, said finite field elements B and C being represented in terms of an optimal normal basis of Type 1 over a field of F₂.spsb.n and said irreducible polynomial f₁ (x) being of degree n, and said field elements B and C being represented as a vector of binary digits, each digit being the co-efficient of the elements arranged in polynomial order, said method comprising:

(a) invoking a function to compute the partial product of said element B with a selected digit of said element C;

(b) monitoring an overflow bit of said partial products;

(c) invoking a function for reducing said partial products by a multiple f₂ (x) of the irreducible f₁ (x) when said overflow occurs and deriving a reduced partial product therefrom;

(d) adding said reduced partial product to said successive partial product;

(e) continuing said steps (c) and (d) for successive digits of said element C to derive a final product;

(f) reducing said final product by said irreducible f₁ (x) if said n^th bit is set.

3. A method of computing the product D of two finite field elements B and C modulo an irreducible polynomial f₁ (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F₂.spsb.n and said irreducible polynomial f₁ (x) being of degree n, said method comprising the steps of:

(a) representing the element B as a vector of binary digits b_i, where b_i is a co-efficient of an i^th basis element of said ONB representation of element B, in polynomial order;

(b) representing said element C as a vector of binary digits c_i, where c_i is a co-efficient of an i^th basis element of said ONB representation of element C, arranged in polynomial order;

(c) initializing a register A;

(d) selecting a digit c_i of said vector C;

(e) computing a partial product vector A of said i^th digit c_i of said element C and the vector B;

(f) adding said partial product to said register A;

(g) shifting said register A

(h) reducing said partial product A by a multiple f₂ (x) of the irreducible polynomial f₁ (x) if bits in a position above n are set;

(i) storing said reduced partial product in said register A;

(j) repeating said steps (e) to (h) for each of said successive bit of said vector C and upon completion said register A containing a final product vector; and

(k) reducing said final product vector A by said irreducible polynomial f₁ (x) if an n^th bit of said register is set.

4. A method as defined in claim 3, said reducing said partial product A includes shifting said bits greater than n to said lower most bit positions and adding said bits thereto.

5. A method as defined in claim 4, said shifting being performed on a word length of bits.

6. A method as defined in claim 5, said adding being an XORing.

7. A method as defined in claim 3, said reducing said partial product A includes testing said (n+1)th bit and shifting said bit said lower most bit positions and adding said bit thereto.

8. A method as defined in claim 3, including storing said vector B in a register.

9. A method as defined in claim 3, said multiple f₂ (x) being represented by f₂ (x)=(x+1)f₁ (x).

10. A method as defined in claim 3, said reducing said final partial product A comprises complementing said component bits to thereby reduce said result to degree (n-1).

11. A method as defined in claim 3, including the step of adding said irreducible f₁ (x) to said vector B if the number of ones(1) bits of said vector is greater than n/2.

12. A method as defined in claim 11, said step comprising complementing said bits up to said component of degree n.

13. A method as defined in claim 3, said bits c_i being selected in decreasing significance.

14. A method as defined in claim 3, said I^th basis element having a form α

².spsp.i.

15. A finite field multiplier for computing the product D of two finite field elements B and C modulo an irreducible polynomial f₁ (x), wherein the finite field elements B and C are represented in terms of an optimal normal basis (ONB) of Type 1 over a field F₂.spsb.n and said irreducible polynomial f₁ (x) being of degree n, comprising:

a) a register B for holding the digits b_i of a vector of binary digits b_i, where b_i is a co-efficient of an i^th basis element of said ONB representation of said element B, arranged in polynomial order;

b) an shift register A for holding a result of said computation and of size at least greater than the degree n of the finite field and for shifting its contents in response to a shift control signal;

c) means for sequentially selecting digits c_i of a vector of binary digits c_i, where c_i is a co-efficient of an i^th basis element of said ONB representation of said element C, arranged in polynomial order, and for generating an add control signal in response to said digit c_i being set; and

d) an arithmetic logic unit(ALU) having a finite field adder circuit responsive to said add control signal, for adding said register B and said register A received as vectors of binary digit inputs and outputting a result of said addition to said shift register A thereby computing a partial product vector A of said i^th digit c_i of said element C and the vector B while adding said result to a previous partial product in said register A and whereby said successive partial products may be reduced by a multiple f₂ (x) of the irreducible polynomial f₁ (x) if bits (n+1) or greater are set by shifting said upper (n+1) bits to a lowermost (n+1) bits of said register A;

said reduced partial products being computed for successive components of said vector C and upon completion said register A containing a final product vector and said final product vector A being reduced by said irreducible polynomial f₁ (x) if an n^th bit of said register is set by applying said complement signal such that said register A represents said product of said two finite field elements B and C modulo f₁ (x).

16. A method of squaring a finite element B modulo an irreducible polynomial f₁ (x), wherein the finite field elements B is represented in terms of an optimal normal basis (ONB) of Type 1 over a field F₂.spsb.n and said irreducible polynomial f₁ (x) being of degree n, said method comprising the steps of:

a) representing the element B as a vector of binary digits b_i, where b_i is a co-efficient the i^th basis element of said ONB representation of element B, arranged in polynomial order;

b) interleaving the binary digits of the representation of element B with zero digits to derive a square thereof;

c) storing in successive cells of a 2n cell shift register the binary digits of the interleaved representation of the element B;

d) reducing said square by a multiple f₂ (x) of the irreducible polynomial f₁ (x).

17. A method as defined in claim 16, said reduction is a cyclic shift of an upper n bits to the lower n bits.

18. A method of squaring a finite element B modulo an irreducible polynomial f₁ (x), wherein the finite field elements B is represented in terms of an optimal normal basis (ONB) of Type 1 over a field F₂.spsb.n and said irreducible polynomial f₁ (x) being of degree n, said method comprising the steps of:

a) representing the element B as a vector of n binary digits b_i, where b_i is a co-efficient the i^th basis element of said ONB representation of element B, arranged in decreasing polynomial order;

b) selecting successive word length sets of said representation;

c) interleaving the binary digits of each said words with zero digits;

d) storing an xor of alternate sets of interleaved words in a register for all such sets; and

e) permuting said stored words to derive a square of said element B therefrom.