Polynomial Basis - Multiplication

Multiplication

Multiplication of two elements in the polynomial basis can be accomplished in the normal way of multiplication, but there are a number of ways to speed up multiplication, especially in hardware. Using the straightforward method to multiply two elements in GF(pm) requires up to m2 multiplications in GF(p) and up to m2 − m additions in GF(p).

Some of the methods for reducing these values include:

• Lookup tables — a prestored table of results; mainly used for small fields, otherwise the table is too large to implement
• The Karatsuba-Ofman algorithm — repeatedly breaking the multiplication into pieces, decreasing the total number of multiplications but increasing the number of additions. As seen above, addition is very simple, but the overhead in breaking down and recombining the parts involved in Karatsuba-Ofman make it prohibitive for hardware, although it is often used in software. It can even be used for general multiplication, and is done in many computer algebra systems such as Waterloo Maple.
• Linear feedback shift register-based multiplication
• Subfield computations — breaking the multiplication in GF(pm) to multiplications in GF(px) and GF(py), where x × y = m. This is not frequently used for cryptographic purposes, since some composite degree fields are avoided because of known attacks on them.
• Pipelined multipliers — storing intermediate results in buffers so that new values can be loaded into the multiplier faster
• Systolic multipliers — using many cells that communicate with neighboring cells only; typically systolic devices are used for computation-intensive operations where input and output sizes are not as important, such as multiplication.