Patent ID: 7003538

Claim:
A method for performing a finite field multiplication of a first Galois element a, having bit places a 0 to a n−1 , provided to a first input register and a second Galois element b, having bit places b 0 to b n−1 , provided to a second input register, the Galois elements a and b belonging to a Galois field GF 2 n described by an irreducible polynomial PR with bit places PR 0 to PR n−1 , comprising forming in an addition part of a Galois multiplier an intermediate result Z of intermediate sums of partial products of bit width 2n−1, said intermediate sums not representing any element of said Galois field, and processing said intermediate result Z in a reduction part of said Galois multiplier by modulo dividing by the irreducible polynomial PR, whereby the result E, with bit places E n−1 to E 0 is computed from the bit places resulting from the modulo dividing by XOR connections and wherein said modulo dividing is carried out in two steps, in a first process stage all bit places Z 2n−2 to Z n are each AND connected with an expanded form PE of the irreducible polynomial PR having bit places PE n−1 to PE 0 and then assembled by a first parallel operating adder tree structure effectively realizing the operation XOR, and these assembled partial results are subsequently each AND connected in a second process stage with the bit places PR n−1 to PR 0 of the irreducible polynomial PR and using a second parallel-operating adder tree structure effecting the logic operation XOR, assembled with the bit places Z n−1 to Z 0 of the intermediate result Z to form the result E with bit places E n−1 to E 0 .