  We show a new algorithm and its implementation for multiplying
bit-polynomials of large degrees. The algorithm is based on evaluating
polynomials at a specific set comprising a natural set for evaluation with
additive FFT and a high order element under Frobenius map of $\mathbb{F}_{2}$.
With the high order element, we can derive more values of the polynomials under
Frobenius map. Besides, we also adapt the additive FFT to efficiently evaluate
polynomials at the set with an encoding process.
  For the implementation, we reorder the computations in the additive FFT for
reducing the number of memory writes and hiding the latency for reads. The
algebraic operations, including field multiplication, bit-matrix transpose, and
bit-matrix multiplication, are implemented with efficient SIMD instructions. As
a result, we effect a software of best known efficiency, shown in our
experiments.
