МОДИФИЦИРОВАННОЕ ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ, ОСНОВАННОЕ НА ПЕРЕСТАНОВКАХ ГРУППЫ КОМПЛЕКСНЫХ КОРНЕЙ ИЗ ЕДИНИЦЫ

В работе рассматривается набор преобразований, которые обобщают известное дискретное преобразование Фурье (ДПФ). Эти обобщения определяются при помощи группы перестановок комплексных корней из единицы. Различным перестановкам соответствуют различные новые ДПФ. На этом пути удается построить преобразования с лучшими по сравнению со стандартным ДПФ спектральными свойствами. Например, для размерности равной четырем, стандартное ДПФ имеет неполный кратный спектр, а большинство новых преобразований имеют простой спектр. Приводятся результаты расчетов параметров преобразований на компьютере, а также некоторые гипотезы об их спектральных свойствах. Рассматривается возможность применения введенных обобщенных преобразований Фурье в криптографии.

дискретное преобразование Фурье, корни из единицы, перестановки, спектр матрицы, собственные вектора, discreet Fourier transform, roots of unity, permutations, matrix spectrum, eigenvectors

1. Ноден П., Китте К. Алгебраическая алгоритмика М.: Мир, 1999.

2. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985.

3. Блэйхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.

4. Berndt B.C., Evans R.J, Williams K.S. Gauss and Jacobi Sums. Wiley and Sons, 1998.

5. Ященко В. (ред.) Введение в криптографию. СПб.: Питер, 2001.

6. Matveev V.B. Intertwining relations between the Fourier transform and discrete Fourier transform // Inverse Problems. 2001. No. 17. P. 633-657.

7. Schur I. Uber die Gaussschen Summen // Nach. Gessel. Gottingen, Math-Phys Klasse. 1921. P. 147-153.

8. Киселев Е.А., Минин Л.А., Новиков И.Я., Ситник С.М. О константах Рисса для некоторых систем целочисленных сдвигов // Математические заметки. 2014. Т. 96. Вып. 2. С. 239-250.

9. Zhuravlev M.V., Kiselev E.A., Minin L.A., Sitnik S.M. Jacobi theta-functions and systems of integral shifts of Gaussian functions // Journal of Mathematical Sciences, Springer. 2011. V. 173. № 2. P. 231-241.

10. Минин Л.А., Журавлев М.В., Ситник С.М. О вычислительных особенностях интерполяции с помощью целочисленных сдвигов гауссовых функций // Научные ведомости Белгородского государственного университета. Математика. Физика. 2009. № 13 (68). Вып. 17/2. С. 89-99.

11. Ситник С.М., Тимашов А.С., Ушаков С.Н. Метод конечномерных приближений в задачах квадратичной экспоненциальной интерполяции // Научные ведомости Белгородского государственного университета. Математика. Физика. 2015. № 17 (214). Вып. 40. С. 130-142.

12. Sitnik S.M. Transmutations and Applications: a survey // arXiv: 1012.37412012. 2012. 141 P.

13. Катрахов В.В., Ситник С.М. Краевая задача для стационарного уравнения Шредингера с сингулярным потенциалом // Доклады Академии наук СССР. 1984. Т. 278. № 4. С. 797-799.

14. Ситник С.М. Факторизация и оценки норм в весовых лебеговых пространствах операторов Бушмана-Эрдейи // ДАН СССР. 1991. Т. 320. № 6. С.1326-1330.

15. Ситник С.М. Компьютерный анализ спектральных свойств модифицированных дискретных преобразований Фурье. // Доклады Адыгской (Черкесской) Международной академии наук. 2007. Т. 9. № 1. C. 98-103.