Method and apparatus for exponentiation over GF(2.sup.n)

A method of squaring a vector in a finite field GF(2.sup.n), the method comprising the steps of:

• a) providing a shift register;
• b) providing feedback means for controlling feedback of elements within the shift register;
• c) shifting a first element of the vector to be squared into the shift register;
• d) shifting a zero into the register;
• e) shifting a subsequent element of the vector to be squared into the shift register;
• and
• f) repeating steps d and e until all elements of the vector to be squares have been shifted into the shift register.

A method of modularly multiplying a first vector by a second vector in a finite field GF(2.sup.n) to form a modular product of the first and second vectors through a single shift, the method comprising the steps of:

• providing a shift register;
• placing the second vector into the shift register;
• calculating components of a modulo primitive polynomial of the first vector;
• providing feedback means, dependant on said components of the modulo primitive polynomial, for controlling feedback of elements within the shift register, wherein said feedback means comprise means for storing said components and means for controlling modular multiplication via said components;
• effecting one shift in said shaft register;
• whereby the contents of the shift register, after the single shift, constitute the modular product of said first and second vectors.

A method for the modular exponentiation of a vector in a finite field GF(2.sup.n), defined by a modulus vector, the method comprising the steps of:

• (a) providing a linear feedback shift register of length n;
• (b) providing a factor vector to be exponentiated, a base vector and an exponent vector, wherein each vector comprises n elements and wherein the base vector is equal to one;
• (c) updating the base vector for each successive element of the exponent vector, the step of updating the base vector comprising:
• i) squaring the base vector, wherein the step of squaring the base vector comprises:
• shifting the elements of the base vector into said linear feedback shift register while inserting the number zero alternatively between each two successive base vector elements, whereby after 2n-1 shifts an n-component modularly squared base vector is generated;
• and
• ii) if element i of the exponent vector equals 1, multiplying the base vector by the factor vector.