16959

Fast Fourier Transforms over Prime Fields of Large Characteristic and their Implementation on Graphics Processing Units

Davood Mohajerani
The University of Western Ontario
The University of Western Ontario, 2017

@phdthesis{mohajerani2016fast,

   title={Fast Fourier Transforms over Prime Fields of Large Characteristic and their Implementation on Graphics Processing Units},

   author={Mohajerani, Davood},

   year={2016},

   school={The University of Western Ontario}

}

Download Download (PDF)   View View   Source Source   

419

views

Prime field arithmetic plays a central role in computer algebra and supports computation in Galois fields which are essential to coding theory and cryptography algorithms. The prime fields that are used in computer algebra systems, in particular in the implementation of modular methods, are often of small characteristic, that is, based on prime numbers that fit on a machine word. Increasing precision beyond the machine word size can be done via the Chinese Remaindering Theorem or Hensel Lemma. In this thesis, we consider prime fields of large characteristic, typically fitting on n machine words, where n 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.
Rating: 2.5. From 1 vote.
Please wait...

Recent source codes

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: