I am looking for the fastest algorithm (in practice) to multiply two polynomials $f(X)\cdot h(X)$ in $\mathbb{F}_p[X]$. The prime $p$ is roughly $256$ bits but the integer $p-1$ might not have any large smooth divisors. The polynomials are of degree less that $2^{30}$.

In the absence of large $2$-power roots of unity in the field, what is the fastest algorithm for this multiplication? Is it still the Schonhage-Strassen algorithm?

I understand that there has been a large body of theoretical results that improve upon Schonhage-Strassen. But the thresholds beyond which they outperform Schonhage-Strassen seem rather high and I am working with prime finite fields of size not much larger than $256$ bits.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.