Score:3

# Fast polynomial multiplication over finite field GF(2^n)

I wonder if there is a more efficient polynomial multiplication than Karatsuba over the finite field $$\operatorname{GF}(2^n)$$. Brief research on this topic gave me a few results on fast multiplication on $$\operatorname{GF}(2^n)$$ using a polynomial over $$\operatorname{GF}(2)$$, however, it was hard to find a fast 'polynomial' multiplication over GF(2^n). (i.e. Multiplication over $$\operatorname{GF}(2^n)[X]$$).

A classic Karatsuba polynomial multiplication would give me a time complexity of $$\mathcal O (N^{(\log 3/\log 2)})$$ but I feel like there should be an algorithm with $$\mathcal O(N\log N)$$ time complexity. Can anybody help me?

-edit

For my case, $$10 \le \log N \le 12$$ and I can set $$n$$ to whatever I want. Also, the modulo arithmetic will be automatically done. (I don't need to care about the slow modulo arithmetic) I found an algorithm achieving $$O(N\log N)$$ time complexity by David Harvey, however it makes use of real number arithmetic with precision as far I understand.

Welcome to Cryptography. In Practice, the Karatsuba has applied a few levels. Then Montgomery or a similar reduction is applied. The performance and choice of algorithms really depend on the case. Are you asking for a specific case or a general case for the known complexity?
@kelalaka It is a specific case, with polynomial degree being 2^10, 2^11, 2^12. I can set the modulus according to the parameter which is power of two!
The $\mathcal O (n \log n)$ for multiplication is recently achieved with a huge constant on the front. At least, we have seen that the complexity of multiplication is not bigger than $\mathcal O (n \log n)$ with a big hidden constant. I've seen an improvement to Karatsuba-Ofman that is only applicable to hardware. Montgomery is a good choice, but it really depends on your application. Maybe you should edit your question with your aim and target and what you found...
See [this paper](https://hal.inria.fr/inria-00188261v4/document) for an overview of fast multiplication approaches on $\mathbb{F}_2[X]$, which also includes how to multiply on $\mathbb{F}_{2^n}$. But for polynomial degrees of around 1024-4096 the advanced approaches are unlikely to be better than Karatsuba or Toom-Cook.
@SamuelNeves Thanks a lot!
While it's in a slightly different setting (integer multiplication vs polynomial multiplication), there have been some indications that you can beat Toom-Cook/Karatsuba using $O(n\log_2 n)$ techniques for general integer multiplication in a relevant parameter range ($>1024$ bits), namely [this](https://eprint.iacr.org/2022/439)
As for multiplication over $R:=GF(2^n)[x]$, one can sometimes improve on Toom-Cook/Karatsuba via using [NTT Friendly Rings](https://eprint.iacr.org/2020/1397). Roughly speaking, you embed $R\hookrightarrow S$ into another ring $S$ that has fast multiplication. This embedding doesn't fully preserve algebraic structure, but provided you are computing some "small" formula in $R$, often one can arrange such that this small formula is always evaluated correctly, i.e. one can use $S$-arithmetic vs $R$-arithmetic at no cost. $S$ arithmetic is often chosen to have $O(n\log_2 n)$ multiplication.
I sit in a Tesla and translated this thread with Ai: