Method for multiplying two factors from the Galois field and multiplier for performing the method
View Patent ↗The invention relates to a method and multiplier for multiplying two factors from the Galois field GF (2 m*p ), where each of the factors can be represented as a vector of p sub-blocks with a width of m bits and p, m are positive integers greater than 1. The method and multiplier allow for a polynomial multiplication to be performed quickly and efficiently with minimum requirements in respect of for storage space. Therefore, savings can thus be achieved in respect of power consumption, crystal surface and calculation time.
1. A multiplier according to the invention for multiplying two factors from the Galois field GF (2 m*p ), where each of the factors can be represented as a vector of p sub-blocks with a width of m bits and p, m are positive integers greater than 1, characterized in that it comprises:
a memory unit for storing the factors to be multiplied of the r least-significant sub-blocks of a reduction polynomial which each comprise m bits, where r is a positive integer less than p, and a reduced final result of the multiplication of the factors,
an m*m-bit multiplier stage for multiplicative linking of each time two of the sub blocks of the factors and for output of a multiplication result with a width of 2m bits,
a first and a second sub-block memory for storage and provision of each time one of the sub-blocks to be linked multiplicatively,
a first intermediate result memory for storing at least one intermediate result,
a first exclusive-OR link stage for linking the m most-significant bits of each multiplication result according to an exclusive-OR function with a digit-aligned selected intermediate result from the first intermediate result memory and with an element selected via a first multiplexer stage,
a second exclusive-OR link stage for linking the m least-significant bits of each multiplication result according to an exclusive-OR function with an element selected via a second multiplexer stage,
a second intermediate result memory for storing a link result output by the second exclusive-OR link stage,
a reduction polynomial memory for storing and provision of the r least-significant sub-blocks of the reduction polynomial,
an output register for temporary storage of one of the link results output by the first or the second exclusive-OR link stage as a sub-block of the reduced end result of the multiplication of the factors to be applied to the memory unit,
a third multiplexer stage for applying the link result output by the first or the second exclusive-OR link stage or a selected sub-block from the memory unit optionally to the reduction polynomial memory, to the first intermediate result memory or to the output register,
a fourth multiplexer stage for optional supply of a sub-block of the reduction polynomial from the reduction polynomial memory or a sub-block of the second factor from the memory unit to the second sub-block memory,
and a control unit to control the said components of the multiplier according to a prespecified functional sequence,
where the first multiplexer stage and the second multiplexer stage each select between the current link result of the second intermediate result memory and a zero vector of the same width.
2. A multiplier as claimed in claim 1 , characterized in that an input of a memory section dimensioned for the link result output by the first exclusive-OR link stage is connected directly to an output of the first exclusive-OR link stage and an output of this memory section is connected to an input of a fifth multiplexer stage via which optionally the link result output by the first exclusive-OR link stage or another intermediate result from the first intermediate result memory is applied to the first exclusive-OR link stage.