Block-serial finite field multipliers

• US 20030093450A1
• Filed: 10/09/2001
• Published: 05/15/2003
• Est. Priority Date: 10/09/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Chin-Long
• Granted Patent: US 6,957,243 B2
• Time in Patent Office: Days
• 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

Finite field elements from the field GF(2^k) are represented as polynomials with binary valued coefficients. As such, multiplication in the field is defined modulo an irreducible polynomial of degree k−1. One of the multiplicands is treated in blocks of polynomials of degree n−1 so that the multiplier operates over T cycles where k=nT. If k is not a composite number to start with, higher order terms are added, so that multipliers are now constructable even when k is prime. Since n<k, the construction of the needed multiplier circuits are much simpler. Designers are now provided with an opportunity of easily trading off circuit speed for circuit complexity in an orderly and structured fashion.

Claims

1. A circuit for performing multiplication of two elements from a finite Galois field GF(2^k) wherein said elements are represented by polynomials a(x) and b(x) and multiplication is carried out modulo an irreducible polynomial p(x) of degree k, said circuit comprising:

a first multiplier modulo p(x) for A_j(x) with (T−

1)≧

j≧

0 and b(x), where A_j(x) is a polynomial of degree n−

1 of the form

$\underset{i=0}{\overset{n-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_{\mathrm{jn}+i}<br><br>x^i$

where a_jn+l is the coefficient for the x^jn+l term in the polynomial a(x) and wherein k=nT;

a summer receiving the output from said multiplier;

a storage means for holding the output from said summer for each of T cycles of operation of said circuit;

a second multiplier modulo p(x) for multiplying the current contents of said storage means by xⁿ, the output of said second multiplier also being supplied as an input to said summer.

2. The circuit of claim 1 further including means to supply in sequential order T successive representations of said polynomials A_j(x), (T−

1)≧

j≧

0, to said first multiplier A<sub>T−

1</sub>(x) being presented first.

3. The circuit of claim 1 wherein said first multiplier multiplies n bit wide representations of A_j(x) with k bit wide representations of b(x).

4. A circuit for performing multiplication of two elements from a finite Galois field GF(2^k) wherein said elements are represented by polynomials a(x) and b(x) and multiplication is carried out modulo an irreducible polynomial p(x) of degree k, said circuit comprising:

a first multiplier modulo p(x) for A_j(x) with (T−

1)≧

j≧

0 and b(x), where A_j(x) is a polynomial of degree n−

1 of the form

$\underset{i=0}{\overset{n-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_{\mathrm{jn}+i}<br><br>x^i$

x^l where a_jn+l is the coefficient for the x^jn+l term in the polynomial a(x) and wherein k is not originally equal to nT but where higher order terms in a(x) are added in sufficient number with zero coefficients to insure that k=nT;

a summer receiving the output from said multiplier;

a storage means for holding the output from said summer for each of T cycles of operation of said circuit;

a second multiplier modulo p(x) for multiplying the current contents of said storage means by xⁿ, the output of said second multiplier also being supplied as an input to said summer.