"Generalizations of the Karatsuba Algorithm for Efficient Implementations" by A. Weimerskirch and C. Paar (https://eprint.iacr.org/2006/224.pdf)
It is faster than mul_naive() and even mul_karatsuba for small polynomial sizes (still N^2 complexity though, so Karatsuba wins for larger sizes). It also does not require the polynomial size to be a power of 2.
It may be possible to get rid of the additional buffer requirement, in which case it will become even faster.
The branch
adk_mulcontains an implementation of arbitrary degree Karatsuba (ADK), inpolynomials.jl::adk_mul().Sources:
It is faster than
mul_naive()and evenmul_karatsubafor small polynomial sizes (stillN^2complexity though, so Karatsuba wins for larger sizes). It also does not require the polynomial size to be a power of 2.It may be possible to get rid of the additional buffer requirement, in which case it will become even faster.