Achieving efficient polynomial multiplication in fermat fields using the fast Fourier transform

ABSTRACT

We introduce an efficient way of performing polynomial multiplication in a class of finite fields GF(p^m) in the frequency domain. The Fast Fourier Transform (FFT) based frequency domain multiplication 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 log log 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 work, we introduce an efficient way of performing polynomial multiplication in finite fields using the FFT. We show that, with careful selection of parameters, all the multiplications required for the FFT computations can be avoided and polynomial multiplication in finite fields can be achieved with only O(m) multiplications in addition to O(m log m) simple shift, addition and subtraction operations. We show that, especially in constrained devices where multiplication is expensive, polynomial multiplication in the suggested finite fields using the FFT outperforms both the schoolbook and Karatsuba methods for practically small finite fields, e.g., relevant to elliptic curve cryptography.

REFERENCES

• 1: R. C. Agarwal and C. S. Burrus. Fast Digital Convolution Using Fermat Transforms. In Southwest IEEE Conf. Rec., pages 538--543, Houston, Texas, USA, April 1973.
• 2: R. C. Agarwal and C. S. Burrus. Fast Convolutions Using Fermat Number Transforms with Applications to Digital Filtering. IEEE Transactions on Computers, ASSP-22(2):87--97, April 1974.
• 3: E. R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, New York, New York, USA, 1968.
• 4: R. E. Blahut. Theory and Practice of Error Control Codes. Addison-Wesley, Reading, Massachusetts, USA, 1983.
• 5: I. Blake, X. Gao, R. Mullin, S. Vanstone, and T. Yaghgoobin. Applications of Finite Fields. Kluwer Academic, 1999.
• 6: J. Cooley and J. Tukey. An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19:297--301, 1965.
• 7: R. Crandall and C. Pomerance. Prime Numbers. Springer-Verlag, New York, NY, USA, 2001.
• 8: A. Karatsuba and Y. Ofman. Multiplication of Multidigit Numbers on Automata. Sov. Phys. Dokl. (English translation), 7(7):595--596, 1963.
• 9: Robert J. McEliece, Finite field for scientists and engineers, Kluwer Academic Publishers, Norwell, MA, 1987
• 10: Alan V. Oppenheim , Ronald W. Schafer , John R. Buck, Discrete-time signal processing (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 11: C. Paar. Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields. PhD thesis, (Engl. transl.), Institute for Experimental Mathematics, University of Essen, Essen, Germany, June 1994. ISBN 3-18-332810-0.
• 12: J. M. Pollard. The Fast Fourier Transform in a Finite Field. Mathematics of Computation, 25:365--374, 1971.
• 13: C. M. Rader. Discrete Convolutions via Mersenne Transforms. IEEE Transactions on Computers, C-21(12):1269--1273, December 1972.
• 14: C. M. Rader. The Number Theoretic DFT and Exact Discrete Convolution. In IEEE Arden House Workshop on Digital Signal Processing, Harriman, New York, January 1972.
• 15: A. Schonhage and V. Strassen. Schnelle Multiplication grosser Zahlen. Computing, 7:281--292, 1971.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials; Computations in finite fields

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Fast Fourier transforms (FFT)

General Terms:
Algorithms, Design, Theory

Keywords:
Fast Fourier Transform (FFT), coding theory, elliptic curve cryptography, fermat numbers, fermat transform, finite fields, polynomial multiplication