Patent ID: 7069287

Claim:
A method for finite field multiplication of odd characteristic extension fields with a microcontroller comprising the steps of: providing a microcontroller comprised of a central processing unit (CPU) having an arithmetic and logical unit (ALU); a multiplier module; an addition module; a division module; and memory locations comprising internal random access memory (RAM) and external random access memory (XRAM); 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 , a 1 , . . . a i , . . . a (m−1) ), B is represented as second array of integer coefficients (b 0 , b 1 , . . . b j , . . . b (m−1) ) and the tuple coefficients a i and b j are elements of the field GF(p) where 0≦i, j≦(m−1); storing said first array in a first memory location; storing said second array in a second memory location; multiplying the two field elements A and B with said multiplier module to produce a product C in a field GF (p m ) where C is represented as a third array of integer coefficients (c 0 , c 1 , . . . c k , . . . c (m−1). and tuple coefficents c k are elements of the field GF(p) where 0≦k≦(m−1); storing said third array in a third memory location; computing m temporary coefficients c k ′ as a sum of m intermediate products without an immediate modular reduction where ∑ 0 m - 1 ⁢ c k ′ = ∑ i + j = k ⁢ a i · b j ; and said intermediate products a i ·b j are computed with said multiplier module; adding said intermediate products for each of temporary coefficient c k ′ with said addition module; storing said temporary coefficients c k ′ in either a fourth memory location or said first, said second or said third memory locations; computing m coefficients c k with said multiplier, addition and division modules by performing a single modular reduction on each of said temporary coefficients c k ′ ; and storing the coefficients c k in either said first, said second, said third or said fourth memory location.