Вычисление преобразований Фурье – Галуа в редуцированных бинарных системах счисления

Abstract

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