Method and apparatus for performing arithmetic in large galois field GF(2n)

Claim 1

A method of controlling errors in an electronically communicated digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ), comprising steps of: a. factoring a composite number n into a set of factors p i wherein the composite number n is a number of bits of each element in the finite field GF(2 n ); b. forming a plurality of primitive polynomials F i wherein each primitive polynomial is of a degree equal to p i and defines a subfield GF(2 pi ) of the finite field GF(2 n ); and c. performing at least one of the plurality of predetermined arithmetic operations on the data message by utilizing an arithmetic circuit coupled to receive the data message, wherein the arithmetic operation is performed in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ).

Claim 2

A method of controlling errors in an electronically communicated digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ), comprising steps of: a. factoring a composite number n into a set of factors p i wherein the composite number n is a number of bits of each element in the finite field GF(2 n ); b. forming a plurality of primitive polynomials F i wherein each primitive polynomial is of a degree equal to p i and defines a subfield GF(2 pi ) of the finite field GF(2 n ); and c. performing at least one of the plurality of predetermined arithmetic operations on the data message by utilizing an arithmetic circuit coupled to receive the data message, wherein the arithmetic operation is performed in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ).

Claim 9

An apparatus for controlling errors in an electronically communicated digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ), comprising: an arithmetic circuit for performing at least one of the plurality of predetermined arithmetic operations on the data message, wherein the arithmetic operation is performed in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ) and wherein each subfield GF(2 pi ) of the plurality of subfields is defined by a primitive polynomial F i of a degree equal to a factor p i of a number of bits of each element in the finite field GF(2 n ).

Claim 10

An apparatus for controlling errors in an electronically communicated digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ), comprising: an arithmetic circuit for performing at least one of the plurality of predetermined arithmetic operations on the data message, wherein the arithmetic operation is performed in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ) and wherein each subfield GF(2 pi ) of the plurality of subfields is defined by a primitive polynomial F i of a degree equal to a factor p i of a number of bits of each element in the finite field GF(2 n ).

Claim 25

A method controlling errors in an electronically communicated digital data message by performing at least one of a plurality of arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ), comprising steps of: a. setting a number of bits in the field, n, equal to Πp i , a composite number, where p i is a set of factors of the number of bits in the field; b. forming a primitive polynomial F 1 over a finite field GF(2) used to represent a p 1 th extension field of the finite field GF(2); c. forming a primitive polynomial F 2 over a finite field GF(2 pi ) used to represent a p 2 th extension field of the finite field GF(2 pi ); d. repeating step c for all factors, p i , of the number of bits in the field, n, until a desired finite field GF(2 n ) is constructed; and e. providing an arithmetic circuit for performing at least one of the plurality of arithmetic operations on the data message in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ).

Claim 26

A method controlling errors in an electronically communicated digital data message by performing at least one of a plurality of arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ), comprising steps of: a. setting a number of bits in the field, n, equal to Πp i , a composite number, where p i is a set of factors of the number of bits in the field; b. forming a primitive polynomial F 1 over a finite field GF(2) used to represent a p 1 th extension field of the finite field GF(2); c. forming a primitive polynomial F 2 over a finite field GF(2 pi ) used to represent a p 2 th extension field of the finite field GF(2 pi ); d. repeating step c for all factors, p i , of the number of bits in the field, n, until a desired finite field GF(2 n ) is constructed; and e. providing an arithmetic circuit for performing at least one of the plurality of arithmetic operations on the data message in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ).

Claim 33

An apparatus for controlling errors in an electronically communicated digital data message by performing at least one of a plurality of arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ) comprising: an arithmetic circuit wherein the arithmetic circuit performs at least one of the plurality of arithmetic operations on the data message in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ) wherein a first subfield GF(2) of the plurality of subfields GF(2 pi ) is represented by a primitive polynomial F 1 having a degree of one, and wherein each of a plurality of successive primitive polynomials F i represents a successive one of the plurality of subfields GF(2 pi ) wherein each of the plurality of successive primitive polynomials F i corresponds to each factor pi of a number of bits in the field n.

Claim 34

An apparatus for controlling errors in an electronically communicated digital data message by performing at least one of a plurality of arithmetic operations on the data message in one or more of a plurality of subfields GF(2 pi ) of a finite field GF(2 n ) comprising: an arithmetic circuit wherein the arithmetic circuit performs at least one of the plurality of arithmetic operations on the data message in one or more of the plurality of subfields GF(2 pi ) of the finite field GF(2 n ) wherein a first subfield GF(2) of the plurality of subfields GF(2 pi ) is represented by a primitive polynomial F 1 having a degree of one, and wherein each of a plurality of successive primitive polynomials F i represents a successive one of the plurality of subfields GF(2 pi ) wherein each of the plurality of successive primitive polynomials F i corresponds to each factor pi of a number of bits in the field n.