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$ – Squeamish Ossifrage Feb 23 '19 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$ – Samuel Neves Feb 23 '19 at 15:24
  • 1
    $\begingroup$ FFT-based GHASH with high bulk throughput (but also high setup overhead): eprint.iacr.org/2014/729 $\endgroup$ – Squeamish Ossifrage Feb 23 '19 at 16:14
  • $\begingroup$ Thank you very much. I will take a look at all this content $\endgroup$ – Pro7ech Feb 24 '19 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.