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

Lukie Boy

10/7/23, 7:23 AM

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.

190

0 + 7

finite-field

montgomery-multiplication

kelalaka

10/7/23, 8:45 AM

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?

Lukie Boy

10/7/23, 8:52 AM

@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!

kelalaka

10/7/23, 9:24 AM

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...

Samuel Neves

10/7/23, 2:10 PM

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.

Lukie Boy

10/8/23, 3:14 PM

@SamuelNeves Thanks a lot!

Mark

10/8/23, 5:17 PM

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)

Mark

10/8/23, 5:19 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.