Sequential Galois multiplication in GF(2n) with GF(2m) Galois multiplication gates

Claim 2

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: a single GF(2 m ) Galois multiplication gate having the Galois subfield GF(2 m ) where m is a positive integral divisor of n having the relationship of k=n/m, where k is a positive integer greater than 1, k>1, which single GF(2 m ) Galois multiplication gate generates k 2 subfield GF(2 m ) Galois partial products; input sequencer means receiving said X and Y n-bit inputs and sequential coupling k m-bit portions of each of said X and Y n-bit inputs to said single GF(2 m ) Galois multiplication gate for enabling said single GF(2 m ) Galois multiplication gate to sequentially generate said k 2 subfield GF(2 m ) Galois partial products therefrom; and, means including constant multiplier means, responsively coupled to said single GF(2 m ) Galois multiplication gate and sequentially accumulating said sequentially generated k 2 subfield GF(2 m ) products for providing on n output lines the n-bit Galois product X·Y.

Claim 3

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: a single GF(2 m ) Galois multiplication gate having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which single GF(2 m ) Galois multiplication gate generates k 2 subfield GF(2 m ) Galois partial products; X input register means for bi-serially receiving said n-bit X input and for sequentially bit-parallelly coupling m-bit portions of said n-bit X input to said single GF(2 m ) Galois multiplication gate; Y input register means for bit-serially receiving said n-bit Y input and for sequentially bit-parallelly coupling m-bit portions of n-bit Y input to said single GF(2 m ) Galois multiplication gate; ·t.sup.2.spsp.m.sup.-2, ·t.sup.2.spsp.m.sup.-3, . . . , ·t.sup.d, . . . , .t.sup.2, ·t, ·1, ·0 constant multiplier means responsively coupled to said single GF(2 m ) Galois multiplication gate for seuentially receiving said k 2 subfield GF(2 m ) Galois partial products and sequentially generating k 2 sets of GF(2 m )·t d or GF(2 m ) ·0 Galois partial products therefrom; and, accumulator means sequentially receiving and accumulating said k 2 sets of subfield GF(2 m )·t d or GF(2 m )·0 Galois partial products for generating and bit-serially outputting said n-bit Galois product X·Y.

Claim 4

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: a single GF(2 m ) Galois multiplication gate having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which single GF(2 m ) Galois multiplication gate generates k 2 subfield GF(2 m ) Galois partial products; X input register means for bi-serially receiving said n-bit X input and for sequentially bit-parallelly coupling m-bit portions of said n-bit X input to said single GF(2 m ) Galois multiplication gate; Y input register means for bit-serially receiving said n-bit Y input and for sequentially bit-parallelly coupling m-bit portions of n-bit Y input to said single GF(2 m ) Galois multiplication gate; ·t.sup.2.spsp.m.sup.-2, ·t.sup.2.spsp.m.sup.-3, . . . , ·t.sup.d, . . . , .t.sup.2, ·t, ·1, ·0 constant multiplier means responsively coupled to said single GF(2 m ) Galois multiplication gate for seuentially receiving said k 2 subfield GF(2 m ) Galois partial products and sequentially generating k 2 sets of GF(2 m )·t d or GF(2 m ) ·0 Galois partial products therefrom; and, accumulator means sequentially receiving and accumulating said k 2 sets of subfield GF(2 m )·t d or GF(2 m )·0 Galois partial products for generating and bit-serially outputting said n-bit Galois product X·Y.

Claim 5

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: GF(2 m ) Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; input sequencer means for receiving said Galois input on said n, X input lines and said Galois input on said n, Y input lines and sequentially coupling m-bit segments of X(X m ) and Y(Y m ) to said GF(2 m ) Galois multiplication gate means; ·t.sup.2.spsp.m.sup.-2, ·t.sup.2.spsp.m.sup.-3, . . . , ·t.sup.d, . . . , ·t.sup.2 ·t, ·1, ·0 constant multiplier means responsively coupled to said GF(2.sup.m) Galois multiplication gate means for sequentially receiving said k.sup.2 subfield GF(2.sup.m) Galois partial products and sequentially generating k.sup.2 sets of GF(2.sup.m)·t.sup.d or GF(2.sup.m)·0 Galois partial products therefrom; n/m multiplexer means, each receiving in parallel, said k 2 sets of GF(2 m )·t d or GF(2 m )·0 Galois products from said constant multiplier means; n/m toggle means, each coupled to a respectively associated one of said n/m multiplexer means for receiving the output therefrom; output register means coupled to each of said n/m toggle means for receiving and formatting the outputs therefrom in an n-bit format, and control sequencer means coupled to said input sequencer means, said n/m multiplexer means and said n/m toggle means for sequentially processing said m-bit segments of X(X m ) and Y(Y m ) from said input sequencer means to form said Galois product X·Y at said output register means.

Claim 6

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: GF(2 m ) Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; input sequencer means for receiving said Galois input on said n, X input lines and said Galois input on said n, Y input lines and sequentially coupling m-bit segments of X(X m ) and Y(Y m ) to said GF(2 m ) Galois multiplication gate means; ·t.sup.2.spsp.m.sup.-2, ·t.sup.2.spsp.m.sup.-3, . . . , ·t.sup.d, . . . , ·t.sup.2 ·t, ·1, ·0 constant multiplier means responsively coupled to said GF(2.sup.m) Galois multiplication gate means for sequentially receiving said k.sup.2 subfield GF(2.sup.m) Galois partial products and sequentially generating k.sup.2 sets of GF(2.sup.m)·t.sup.d or GF(2.sup.m)·0 Galois partial products therefrom; n/m multiplexer means, each receiving in parallel, said k 2 sets of GF(2 m )·t d or GF(2 m )·0 Galois products from said constant multiplier means; n/m toggle means, each coupled to a respectively associated one of said n/m multiplexer means for receiving the output therefrom; output register means coupled to each of said n/m toggle means for receiving and formatting the outputs therefrom in an n-bit format, and control sequencer means coupled to said input sequencer means, said n/m multiplexer means and said n/m toggle means for sequentially processing said m-bit segments of X(X m ) and Y(Y m ) from said input sequencer means to form said Galois product X·Y at said output register means.

Claim 7

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: GF(2 m )Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; X input register means for bit-serially receiving said n-bit X input and for sequentially bit-paralelly coupling m-bit portions of said n-bit X input to said GF(2 m ) Galois multiplication gate means; Y input register means for bit-serially receiving said n-bit Y input and for sequentially bit-parallelly coupling m-bit portions of said n-bit Y input to said GF(2 m ) Galois multiplication gate means; X m ·Y m register means for receiving and storing said k 2 subfield GF(2 m ) Galois partial products from said GF(2 m ) multiplication gate means; ·t d constant multiplier means receiving said k 1 subfield GF(2 n ) Galois partial products from said X m ·Y m register means for performing the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial products; Galois sum means for receiving the output of said ·t d constant multiplier means; output register means for receiving said storing the output of said Galois sum means; and, multiplexer means sequentially coupling the contents of said output register means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said ·t d constant multiplier means and said output register means for each of said k 2 subfield GF(2 m ) Galois partial products and generating in said output register means said Galois product X·Y.

Claim 8

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: GF(2 m )Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; X input register means for bit-serially receiving said n-bit X input and for sequentially bit-paralelly coupling m-bit portions of said n-bit X input to said GF(2 m ) Galois multiplication gate means; Y input register means for bit-serially receiving said n-bit Y input and for sequentially bit-parallelly coupling m-bit portions of said n-bit Y input to said GF(2 m ) Galois multiplication gate means; X m ·Y m register means for receiving and storing said k 2 subfield GF(2 m ) Galois partial products from said GF(2 m ) multiplication gate means; ·t d constant multiplier means receiving said k 1 subfield GF(2 n ) Galois partial products from said X m ·Y m register means for performing the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial products; Galois sum means for receiving the output of said ·t d constant multiplier means; output register means for receiving said storing the output of said Galois sum means; and, multiplexer means sequentially coupling the contents of said output register means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said ·t d constant multiplier means and said output register means for each of said k 2 subfield GF(2 m ) Galois partial products and generating in said output register means said Galois product X·Y.

Claim 9

The Galois GF(2 n ) multiplication gate of claim 4 in which said GF(2 m ) multiplication gate means is a PROM.

Claim 10

The Galosis GF(2 n ) multiplication gate of claim 4 in which said ·t d constant multiplier means is a ·t d PROM means.

Claim 11

The Galois GF(2 n ) multiplication gate of claim 6 further including ·t d Select PROM means coupled to said ·t d PROM means for enabling said ·t d PROM means to select the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial products.

Claim 12

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: GF(2m) Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; X input means for receiving said n-bit X input and for sequentially coupling m-bit portions of said n-bit X input to said GF(2 m ) Galois multiplication gate means; Y input means for receiving said n-bit Y input and for sequentially coupling m-bit portions of said n-bit Y input to said GF(2 m ) Galois multtiplication gate means; X m ·Y means for receiving and storing said k 2 subfield GF(2 m ) Galois partial products from said GF(2 m ) multiplication gate means; ·t d constant multiplier means receiving said k 2 subfield GF(2 m ) Galois partial products from said X m ·Y m means for performing the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial products; Galois sum means for receiving the output of said ·t d constant multiplier means; output means for receiving and storing the output of said Galois sum means; and, multiplexer means sequentially coupling the contents of said output means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said ·t d constant multiplier means and said output means for each of said k 2 subfield GF(2 m ) Galois partial products and generating in said output means said Galois product X·Y.

Claim 13

A Galois GF(2 n ) multiplication gate for performing the Galois multiplication in the Galois field GF(2 n ) which Galois GF(2 n ) multiplication gate generates the Galois product X·Y=(X·Y) 0 , . . . , (X·Y) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 and from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 comprising: GF(2m) Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; X input means for receiving said n-bit X input and for sequentially coupling m-bit portions of said n-bit X input to said GF(2 m ) Galois multiplication gate means; Y input means for receiving said n-bit Y input and for sequentially coupling m-bit portions of said n-bit Y input to said GF(2 m ) Galois multtiplication gate means; X m ·Y means for receiving and storing said k 2 subfield GF(2 m ) Galois partial products from said GF(2 m ) multiplication gate means; ·t d constant multiplier means receiving said k 2 subfield GF(2 m ) Galois partial products from said X m ·Y m means for performing the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial products; Galois sum means for receiving the output of said ·t d constant multiplier means; output means for receiving and storing the output of said Galois sum means; and, multiplexer means sequentially coupling the contents of said output means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said ·t d constant multiplier means and said output means for each of said k 2 subfield GF(2 m ) Galois partial products and generating in said output means said Galois product X·Y.

Claim 14

The Galois GF(2 n ) multiplication gate of claim 8 further including ·t d Select means coupled to said ·t d constant multiplier means for enabling said ·t d constant multiplier means to select the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial products.

Claim 15

A Galois GF(2 n ) linear gate for performing the Galois linear operation in the Galois field GF(2 n ) which Galois GF(2 n ) linear gate generates the Galois linear resultant X·Y+Z=(X·Y+Z) 0 , . . . , (X·Y+Z) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 and from the Galois input on n, Z input lines Z.sub.0, . . . , Z.sub.n-1 comprising: a single GF(2 m ) Galois multiplication gate having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which single GF(2 m ) Galois multiplication gate generates k 2 subfield GF(2 m ) Galois partial products; input sequencer means receiving said X and Y n-bit inputs and sequential coupling k m-bit portions of each of said X and Y n-bit inputs to said single GF(2 m ) Galois multiplication gate for enabling said single GF(2 m ) Galois multiplication gate to sequentially generate said k 2 subfield GF(2 m ) Galois partial products therefrom; and, means, including constant multiplier means, responsively coupled to said single GF(2 m ) Galois multiplication gate and to said Z n-bit inputs for sequentially accumulating said sequentially generated k 2 subfield GF(2 m ) partial products and providing on n output lines the n-bit Galois linear resultant X·Y+Z.

Claim 16

A Galois GF(2 n ) linear gate for performing the Galois linear operation in the Galois field GF(2 n ) which Galois GF(2 n ) linear gate generates the Galois linear resultant X·Y+Z=(X·Y+Z) 0 , . . . , (X·Y+Z) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 and from the Galois input on n, Z input lines Z.sub.0, . . . , Z.sub.n-1 comprising: a single GF(2 m ) Galois multiplication gate having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which single GF(2 m ) Galois multiplication gate generates k 2 subfield GF(2 m ) Galois partial products; input sequencer means receiving said X and Y n-bit inputs and sequential coupling k m-bit portions of each of said X and Y n-bit inputs to said single GF(2 m ) Galois multiplication gate for enabling said single GF(2 m ) Galois multiplication gate to sequentially generate said k 2 subfield GF(2 m ) Galois partial products therefrom; and, means, including constant multiplier means, responsively coupled to said single GF(2 m ) Galois multiplication gate and to said Z n-bit inputs for sequentially accumulating said sequentially generated k 2 subfield GF(2 m ) partial products and providing on n output lines the n-bit Galois linear resultant X·Y+Z.

Claim 17

A Galois GF(2 n ) linear gate for performing the Galois linear operation in the Galois field GF(2 n ) which Galois GF(2 n ) linear gate generates the Galois linear resultant X·Y+Z=(X·Y+Z) 0 , . . . , (X·Y+Z) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 and from the Galois input on n, Z input lines Z.sub.0, . . . , Z.sub.n-1 comprising: GF(2 m ) Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; X input means for receiving said n-bit X input and for sequentially coupling m-bit portions of said n-bit X input to said GF(2 m ) Galois multiplication gate means; Y input means for receiving said n-bit Y input and for sequentially coupling m-bit portions of said n-bit Y input to said GF(2 m ) Galois multiplication gate means; X m ·Y m means for receiving and storing said k 2 subfield GF(2 m ) Galois partial products from said GF(2 m ) multiplication gate means; Z input means for receiving said n-bit Z input and for sequentially coupling m-bit portions of said n-bit Z input to said X m ·Y m means; said X m ·Y m means forming k 2 subfield GF(2 m ) Galois partial resultants from said k 2 subfield GF(2 m ) Galois partial products and said m-bit portions of said n-bit Z input; ·t d constant multiplier means receiving said k 2 subfield GF(2 n ) Galois partial resultants from said X m ·Y m means for performing the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial resultants; Galois sum means for receiving the output of said ·t d constant multiplier means; output means for receiving and storing the output of said Galois sum means; and, multiplexer means sequentially coupling the contents of said output means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said ·t d constant multiplier means and said output means for each of said k 2 subfield GF(2 m ) Galois partial resultants and generating in said output means said Galois linear resultant X·Y+Z.

Claim 18

A Galois GF(2 n ) linear gate for performing the Galois linear operation in the Galois field GF(2 n ) which Galois GF(2 n ) linear gate generates the Galois linear resultant X·Y+Z=(X·Y+Z) 0 , . . . , (X·Y+Z) n-1 from the Galois input on n, X input lines X.sub.0, . . . , X.sub.n-1 from the Galois input on n, Y input lines Y.sub.0, . . . , Y.sub.n-1 and from the Galois input on n, Z input lines Z.sub.0, . . . , Z.sub.n-1 comprising: GF(2 m ) Galois multiplication gate means having the Galois subfield GF(2 m ), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2 m ) Galois multiplication gate means generates k 2 subfield GF(2 m ) Galois partial products; X input means for receiving said n-bit X input and for sequentially coupling m-bit portions of said n-bit X input to said GF(2 m ) Galois multiplication gate means; Y input means for receiving said n-bit Y input and for sequentially coupling m-bit portions of said n-bit Y input to said GF(2 m ) Galois multiplication gate means; X m ·Y m means for receiving and storing said k 2 subfield GF(2 m ) Galois partial products from said GF(2 m ) multiplication gate means; Z input means for receiving said n-bit Z input and for sequentially coupling m-bit portions of said n-bit Z input to said X m ·Y m means; said X m ·Y m means forming k 2 subfield GF(2 m ) Galois partial resultants from said k 2 subfield GF(2 m ) Galois partial products and said m-bit portions of said n-bit Z input; ·t d constant multiplier means receiving said k 2 subfield GF(2 n ) Galois partial resultants from said X m ·Y m means for performing the appropriate constant multiply for each of said k 2 subfield GF(2 m ) Galois partial resultants; Galois sum means for receiving the output of said ·t d constant multiplier means; output means for receiving and storing the output of said Galois sum means; and, multiplexer means sequentially coupling the contents of said output means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said ·t d constant multiplier means and said output means for each of said k 2 subfield GF(2 m ) Galois partial resultants and generating in said output means said Galois linear resultant X·Y+Z.