Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Achieving Efficient Polynomial Multiplication in Finite Fields Using the Fast Fourier Transform

 

Selcuk Baktir

Cryptography & Information Security Laboratory
Electrical & Computer Engineering Department
Worcester Polytechnic Institute

Finite fields have many applications in coding theory, cryptography and digital signal processing. Therefore, efficient implementation of their arithmetic is desired. In this talk we will present an efficient way of performing polynomial multiplication in finite fields in the frequency domain. The Fast Fourier Transform (FFT) based technique, originally proposed for integer multiplication, provides an extremely efficient method for multiplication with the best known asymptotic complexity, i.e. O(n log_n loglog_n). Unfortunately, the original FFT method bears significant overhead due to the conversions between the time and the frequency domains, which makes it impractical to perform multiplication of relatively short (160-1024 bits) integer operands as used in many applications. In this talk, we will introduce an efficient way of performing polynomial multiplication over finite fields using the FFT technique. We will show that, with careful selection of parameters, all multiplications required for the FFT computations can be avoided and polynomial multiplication over finite fields can be achieved with only O(m) multiplications in addition to O(m log_m) simple shift, addition and subtraction operations. Thus, we will show that finite field polynomial multiplication using the FFT outperforms both the schoolbook method and the Karatsuba algorithm for practical cases.

 

DATE: January 24, 2005, Monday @ 13:30
PLACE: EA 409