Big Prime Field FFT on the GPU
Liangyu Chen, Svyatoslav Covanov, Davood Mohajerani, Marc Moreno Maza · 2017
We consider prime fields of large characteristic, typically fitting on $k$ machine words, where k is a power of 2. When the characteristic of these fields is restricted to a subclass of the generalized Fermat numbers, we show that arithmetic operations in such fields offer attractive performance, both in terms of algebraic complexity and parallelism. In particular, these operations can be vectorized, leading to efficient implementation of fast Fourier transforms on graphics processing units.