This article is cited in 56 papers

Information Theory and Coding Theory

Method for the Fast Fourier Transform Evaluation over a Finite Field

P. V. Trifonov, S. V. Fedorenko

Saint-Petersburg State Polytechnical University

Abstract: We consider the problem of fast computation of the Fourier transform over a finite field by decomposing an arbitrary polynomial into a sum of linearized polynomials. Examples of algorithms for the Fourier transform with complexity less than that of the best known analogs are given.

UDC: 621.391.1:681.3

Received: 25.10.2002
Revised: 05.02.2003

 English version: Problems of Information Transmission, 2003, 39:3, 231–238

Bibliographic databases:

• 
•