Patent Document ID: 20020062330
Application ID: 09956755
Patent Flag: 0

Claim One:
1. A method for finite field multiplication of odd characteristic extension fields comprising the steps of: selecting a basis representation of field elements; providing at least two field elements A and B in a field GF (p m ) represented as m-tuples where p>2, m>1, A is represented as an first array of integer coefficients (a 0 &plus;a 1 &plus;... &plus;a 1... &plus;a (m−1) ), B is represented as second array of integer coefficients (b 0 &plus;b 1 &plus;... &plus;b j &plus;... &plus;b (m−1) ) and the tuple coefficients a i and b j are elements of the field GF(p) where 0&lE;i, j&lE;(m−1); multiplying the two field elements A and B to produce a product C in a field GF (p m ) where C is represented as a third array of integer coefficients (c 0 &plus;c 1 &plus;... &plus;c k &plus;... &plus;c (m−1) and tuple coefficents c k are elements of the field GF(p) where 0&lE;k&lE;(m−1); computing m temporary coefficients c k as a sum of m intermediate products without an immediate modular reduction where 3 &Sum; 0 m - 1 &it; c k ′ = &Sum; i + j = k &it; a i &CenterDot; b j ; adding said intermediate products for each of temporary coefficient c k ; and computing m coefficients c k by performing a single modular reduction on each of said temporary coefficients c k.