Is there something similar (or an other efficient approach) to the NTT for the multiplication of polynomials in polynomial rings modulo $X^{2^n} + 1$ with coefficients in $\operatorname{GF}(p)$ with $p \equiv 1 \pmod{2^{n+1}}$, but instead for polynomial rings with coefficients in $\operatorname{GF}(2^s)$?

  • 1
    $\begingroup$ Not NTT, but you might be interested to see how BearSSL computes $\operatorname{GF}(2^{128})$ arithmetic for GHASH in software: crypto.stackexchange.com/a/66462 $\endgroup$ Feb 23, 2019 at 14:20
  • 1
    $\begingroup$ On characteristic 2 additive FFTs serve this purpose. Chapter 3 of Mateer's thesis has a number of these, and several others have been discovered since then. $\endgroup$ Feb 23, 2019 at 15:24
  • 1
    $\begingroup$ FFT-based GHASH with high bulk throughput (but also high setup overhead): eprint.iacr.org/2014/729 $\endgroup$ Feb 23, 2019 at 16:14
  • $\begingroup$ Thank you very much. I will take a look at all this content $\endgroup$
    – user51428
    Feb 24, 2019 at 9:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.