Putting Fürer's Algorithm into Practice with the BPAS Library

Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as other disciplines. In 1971, Schönhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most n bits to O(log n log log n). In 2007, Martin Fürer presented a new algorithm that runs in O (n log n · 2 ^O(log* n)) , where log*n is the iterated logarithm of n. We explain how we can put Fürer’s ideas into practice for multiplying polynomials over a prime field Z/pZ, which characteristic is a Generalized 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 that multiplication inside such a prime field can be efficiently implemented via Fast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formula and the fact that r is a 2k-th primitive root of unity, we obtain an efficient implementation of FFT over Z/pZ. This implementation outperforms comparable implementations either using other encodings of Z/pZ or other ways to perform multiplication in Z/pZ.

Name thesis:degree_name

M Sc

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

The University of Western Ontario

Year dc:date.issued

2018

Author dc:creator

• Wang, Linxiao

Advisor dc:contributor.advisor

• Moreno Maza, Marc

• Furer's algorithm
• Fast Fourier Transform
• Generalized Fermat prime
• Polynomial multiplication

Language dc:language.iso

en_ca

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14721/28127

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/28127