method and device for reduction of a polynomial in a binary finite field, especially in the context of a cryptographic application

摘要

The invention relates to a fast, chip space-saving method for reducing a first data word that corresponds to a polynomial C(x) and has a maximum length 2n-1, to a second data word with a maximum length m, said second data word corresponding to a polynomial C'0(x) that is equivalent to C(x) in a binary finite field GF(2m), whose elements have a maximum length m, where m is either less than or equal to n. According to said method, the first data word is sub-divided into a binary first sub-data word C0 and a binary second sub-data word C1, C1 is subjected to an iterative right-shift to form terms of the sum until a respective term of the sum is assigned to each non-disappearing term of a reduction trinomial or pentanomial, which does not equal the term xm, the terms of the sum formed for the first sub-data word are added together to form a total data word and the method steps are then repeated from the sub-division step to the creation of the total data word, until the total data word that has been determined has a maximum length m, thus forming the desired second data word.