Evaluating Bernstein–Rabin–Winograd polynomials

We describe an algorithm which can efficiently evaluate Bernstein–Rabin–Winograd (BRW) polynomials. The presently best known complexity of evaluating a BRW polynomial on \(m\ge 3\) field elements is \(\lfloor m/2\rfloor \) field multiplications. Typically, a field multiplication consists of a basic multiplication followed by a reduction. The new algorithm requires \(\lfloor m/2\rfloor \) basic multiplications and \(1+\lfloor m/4\rfloor \) reductions. Based on the new algorithm for evaluating BRW polynomials, we propose two new hash functions \({\textsf {BRW}}128\) and \({\textsf {BRW}}256\) with digest sizes 128 bits and 256 bits respectively. The practicability of these hash functions is demonstrated by implementing them using instructions available on modern Intel processors. Timing results obtained from the implementations suggest that \({\textsf {BRW}}\) based hashing compares favourably to the highly optimised implementation by Gueron of Horner’s rule based hash function.