  In ISSAC 2017, van der Hoeven and Larrieu showed that evaluating a polynomial
P in GF(q)[x] of degree <n at all n-th roots of unity in GF($q^d$) can
essentially be computed d-time faster than evaluating Q in GF($q^d$)[x] at all
these roots, assuming GF($q^d$) contains a primitive n-th root of unity. Termed
the Frobenius FFT, this discovery has a profound impact on polynomial
multiplication, especially for multiplying binary polynomials, which finds
ample application in coding theory and cryptography. In this paper, we show
that the theory of Frobenius FFT beautifully generalizes to a class of additive
FFT developed by Cantor and Gao-Mateer. Furthermore, we demonstrate the power
of Frobenius additive FFT for q=2: to multiply two binary polynomials whose
product is of degree <256, the new technique requires only 29,005 bit
operations, while the best result previously reported was 33,397. To the best
of our knowledge, this is the first time that FFT-based multiplication
outperforms Karatsuba and the like at such a low degree in terms of
bit-operation count.
