English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Fast algorithms for integer and polynomial multiplication play an importantrole in scientific computing as well as in other disciplines. In 1971,Sch{\"o}nhage and Strassen designed an algorithm that improved themultiplication time for two integers of at most $n$ bits to $\mathcal{O}(\log n\log \log n)$. In 2007, Martin F\"urer presented a new algorithm that runs in$O \left(n \log n\ \cdot 2^{O(\log^* n)} \right)$, where $\log^* n$ is theiterated logarithm of $n$.  We explain how we can put F\"urer's ideas into practice for multiplyingpolynomials over a prime field $\mathbb{Z} / p \mathbb{Z}$, for which $p$ is aGeneralized Fermat prime of the form $p = r^k + 1$ where $k$ is a power of $2$and $r$ is of machine word size. When $k$ is at least 8, we show thatmultiplication inside such a prime field can be efficiently implemented viaFast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formulaand the fact that $r$ is a $2k$-th primitive root of unity in $\mathbb{Z} / p\mathbb{Z}$, we obtain an efficient implementation of FFT over $\mathbb{Z} / p\mathbb{Z}$. This implementation outperforms comparable implementations eitherusing other encodings of $\mathbb{Z} / p \mathbb{Z}$ or other ways to performmultiplication in $\mathbb{Z} / p \mathbb{Z}$.

Putting F\"urer Algorithm into Practice with the BPAS Library