Full text of article: Russian language.

Abstract:
It is proved the existence of «exclusive» prime numbers, for which Rader-Winograd algorithms of discrete Fourier transform and/or convolution computation for corresponded lengths are not effective. The sufficient conditions of «exclusiveness» are given in analytical form.

Key words: discrete Fourier transform, cyclotomic convolution, Rader-Winograd algorithm, computational complexity.

References:

1. Blahut, R.E. Fast algorithms for Digital Signal Processing / R.E. Blahut. – Addison-Wesley, 1985.
2. McClellan, J.H. Number Theory in Digital Signal Processing / J.H. McClellan, C.M. Rader. – Prentice-Hall, New Jersey, 1979.
3. Winograd, S. On Computing the Discrete Fourier Transform / S. Winograd // Proc. Nat. Acad. Sci. USA. – 1976. – Vol.73. – P.1005-1006.
4. Winograd, S. On the Discrete Fourier Transform / S. Winograd // Math. Comp. – 1978. – Vol. 32. – P. 175-199.
5. Vlasenko, V.A. Methods of Fast Convolution Algorithms Synthesis and Spectral Signal Analysis / V.A. Vlasenko, Yu.P. Lappa, L.P. Yaroslavsky. – Moscow, Science, 1990. – 180 p. – (In Russian).
6. Nussbaumer, H.J. Fast Fourier Transform and Convolution Algorithms / H.J. Nussbaumer. – Springer-Verlag, Berlin, 1982.
7. Erdös, P. On the normal number of prime factors of p-1 and some related problems concerning Euler's φ-function / P. Erdös // Quart. J. Oxford. – 1935.– Vol.6. – P. 205-213.
8. Prachar, K. Primzahlverteilung / K.Prachar. – Springer-Verlag, Berlin, 1957.
9. Winograd, S. Arithmetic complexity of computations / S. Winograd. – SIAM, 1980. – 93p.
10. Dubner, H. Large Sophie Germain Primes / H. Dubner. // Math. Comput. – 1996. – Vol. 65. –P. 393-396.
11. Indlekofer, K. H. Largest Known Twin Primes and Sophie Germain Primes / K. H. Indlekofer, A. Járai // Math. Comput. – 1999. – Vol. 68. – P. 1317-1324.
12. Ribenboim, P. Sophie Germain Primes / P. Ribenboim // The New Book of Prime Number Records. – New York, Springer-Verlag, 1996. – P. 329-332.
13. Chernov, V.M. Data Algorithms: Galois vs. Rader and Winograd / V.M.Chernov // Pattern Recognition and Image Analysis. – 2003. – Vol. 13(1) . – P. 5–7.
14. Chernov, V.M. Arithmetic methods of fast discrete orthogonal transform synthesis / V.M. Chernov. – Moscow, Fizmatlit, 2007. – (In Russian).
15. Chernov, V. Fast algorithm for «error-free» convolution computation using Mersenne-Lucas codes / V. Chernov // Chaos, Solitons and Fractals. – 2006. – Vol. 29. – P. 372-380.

---

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20