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

Основной объект исследования работы – преобразования Фурье–Галуа (синонимы: теоретико-числовые преобразования, ТЧП) [1, 2], являющиеся модулярной версией дискретного преобразования Фурье в конечном поле (mod p ):

N - 1

xˆ(m) = ∑ x(n)ωmn , n=0

ω ^N ≡ 1(mod p ),                               (1)

x ( n ) ∈ Z , m = 0,1,...N - 1.

Считалось, что такие преобразования были введены в [3] в 1972, пока не было обнаружено, что такое преобразование было использовано Штрассеном и Шёнхаге в работе по умножению больших целых чисел [4] в 1966 году (заметим, что их приоритет иногда оспаривается также с упоминанием работ Фараджие-ва и Цыпкина 1965-1966 гг. См., например, [5]).

Преобразования (1) обладают рядом полезных свойств, главное из которых – отсутствие вычислительной погрешности, что, например, для задач, возникающих в криптографии, является принципиальным. Пик популярности исследований ТЧП приходился на 90-е годы, причём эти исследования не ограничивались только теоретическими. Наряду с ними проводились и аппаратные разработки [6].

Следует отметить, что, в отличие от традиционного «комплексного» дискретного преобразования Фурье (ДПФ), его модулярная версия (1) обладает рядом специфических недостатков, затрудняющих его вычисление:

• •    операции (mod p ) не являются «элементарными» компьютерными операциями;

• •    длина преобразования и простое число p связаны соотношением делимости N | ( p – 1);

• •    зачастую делители числа ( p – 1) таковы, что вычисление (1) исключает дополнительную алгоритмическую поддержку за счёт применения модулярных аналогов быстрых алгоритмов ДПФ.

В ряде случаев удаётся выбрать параметры преобразования (в частности, простое число p ), при которых перечисленные выше вычислительные недостатки проявляются в минимальной степени.

Наиболее известны в этом контексте простые числа Ферма p = 2 ^B + 1, B = 2 ^k , простые числа Мерсенна p = 2 ^k – 1, по модулю которых в соответствующих конечных полях относительно просто реализуются арифметические операции при представлении элементов этих полей в бинарной арифметике со множеством цифр Λ = {0, 1} [1, 2]. Менее известны простые числа Голомба [7] p = 3 ⋅ 2 ^k + 1 и Люка p = 5 ⋅ 2 ^k + 1, для которых также возможна не очень сложная реализация операций в бинарной системе счисления, и вообще для простых чисел p = 2 ⁿ – 2 ^m + 1 [5]. Естественно, что для этих чисел наиболее эффективная реализация в двоичной {0,1}-арифметике будет при ω ≡ 2(mod p ) , когда умножения на степени ω сводятся к регистровым сдвигам.

Замечание. К сожалению, достаточно общие утверждения о мультипликативных порядках элементов ω ≡ 2(mod p ) , то есть о возможных длинах преобразования (1), известны только в простейших случаях. В общем случае эта задача сводится к вычислительно сложной задаче дискретного логарифмирования.

Рассмотрение в преобразовании (1) вместо простых p составных модулей mod m добавляет к отмеченным трудностям необходимость учёта возможных делителей нуля фактор-кольца Z / m Z . Эта проблема решается, как правило, с помощью распараллеливания вычислений по модулям, равным делителям числа m .

В работах [8 – 10] идея распараллеливания реализуется также в сочетании с представлением элементов кольца Z / m Z в подходящей системе счисления.

Необходимые теоретические сведения и обозначения

Пусть Z ( d )– кольцо целых квадратичных чисел поля Q ( d ), то есть чисел z = a + b^d ; a , b e Q с условиями:

Norm( z ) = a ² - b ² d e Z , Tr ( z ) = 2 a e Z .

Как известно [13],

Z ( ^/ d ) = { z = a + bid } =

J       { z : a , b e Z при d * 1(mod4) } ;

[ { z : a , b e Z , a = b (mod2) при d ^ 1(mod4) } .

Согласно [14], элемент ae Z ( d ) называется основанием канонической системы счисления в Z ( d ),если любой элемент z этого кольца представим в виде

k ^{( z} ) )

z=E zka k, zkeЛ.                            (2)

k = 0

Числа z k , допуская некоторую методологическую вольность, будем называть цифрами , множество Л - цифровым алфавитом, а пару ( a , Л ) - системой счисления в кольце Z ( d ). Если

Л = { 0,1,..., |Norm( a )| - 1 } ,                         (3)

то система счисления называется канонической системой счисления. Исчерпывающее описание канонических систем счисления для мнимых квадратичных полей получено в [13].

В работе [14] было предложено обобщение понятия канонической системы счисления: допускался цифровой алфавит Л , являющийся конечным подмножеством множества Z ( d ). Такие системы счисления, следуя [14], будем называть квазиканониче-скими системами счисления.

Как легко следует из ограничений классификационных теорем работы [13], бинарные канонические системы счисления существуют только в кольцах

Z ( i ), Z ( i 2), Z ( i 7).                               (4)

В [14] показано, что в этих кольцах и только в них существуют и квазиканонические системы счисления. Определить цифры z k разложения (2) можно с помощью рекуррентного процесса [15], [10], но для рассматриваемых колец Z ( d ) лучше воспользоваться алгоритмом деления по норме на элемент a [12]. Такой алгоритм реализуем лишь для пяти значений d ≤ 0, а именно: d = –1, –2, –3, –7, –11, то есть и для рассматриваемых колец (4).

Пусть далее для данного простого p число d является квадратичным вычетом (mod p) [17], то есть существуют решения сравнения y2 ^ d (mod p). (5)

Пусть n - одно из решений сравнения (5), рассмотрим гомоморфизм

Ф : z = a + b4d ^ a + n b (mod p ), (6) так как элемент в правой части (6) принадлежит конечному полю F _p , то есть ф - отображение Z (T d ) ^ F p .

Отображение ф редукция (mod p ), очевидным образом индуцирует преобразование представления (1) с новыми параметрами: цифрами ф ( z k ) и основанием Ф ( a ) = g. Такие представления будем называть представлениями в редуцированных системах счисления.

В настоящей работе рассматриваются только бинарные редуцированные системы счисления (то есть с двухэлементными цифровыми множествами Л ).

Свяжем с элементом кольца F p его код – вектор цифр:

• ^    = - g ⁰ + 5 1 g ¹ + ^ 2 g ² + ... ^ (U 5 1 , ^ --- ) . (7)

Операции над представлениями элементов (2) индуцируют соответствующие им правила преобразований кодов. Отметим, что при такой интерпретации цифры ^ k при реализации операций играют не роль чисел, а являются исключительно «идентификаторами состояния соответствующего триггера».

Конечные поля, для которых существуют бинарные редуцированные системы счисления

Рассмотрим подробнее те из колец целых квадратичных чисел Z ( d ), для которых выполняются условия:

• (a)    число ( d ) является квадратичным вычетом (mod p ),

• (b)    в кольце Z ( d ) существуют бинарные ква-зиканонические системы счисления.

Колец Z ( d ) с условием (b) немного: Z ( i ), Z ( i 2), Z ( i 7). Исследуем, при каких простых p каждое из перечисленных колец удовлетворяет условию (a).

Случай поля Z _p ( i ) = F _p . Как следует из работы [13] о канонических системах счисления в мнимых квадратичных полях и её обобщений [16] на «квази-канонические» системы счисления, в кольце целых элементов Z ( i ) существуют ровно 8 бинарных «ква-зиканонических» систем счисления, а именно системы счисления с основаниями a = a ± = -1 ± i и множествами Л цифр

{ 0,1 } , { 0, i } , { 0, - 1 } , { 0, - i } .

В табл. 1 указаны правила инверсии знака, переноса в старший разряд(ы) для четырех из восьми бинарных систем счисления.

Табл. 1. Арифметические операции в квазиканонических системах счисления кольца целых квадратичных Z (i)

Система счисления { a , Л }	Преобразование выражений, возникающих при реализации арифметических операций
a = - 1 + i , Л = { 0, i }	i = i a + i , 432 - 1 = i a + 1 a + 1 a + 1 , 2 i = i a 3 + i a 2
a = - 1 + i , Л = { 0, - 1 }	( - 1 ) 2 = 1 = = ( - 1) a 4 + ( - 1) a 3 + ( - 1) a 2 + ( - 1), - 2 = ( - 1 ) a 3 + ( - 1 ) a 2
a = - 1 + i , Л = { 0, - i }	( - i ) 2 = - 1 = = ( - i ) a 2 + ( - i ) a + ( - i ) , i = ( - i ) a 4 + ( - i ) a 3 + + (- i )a 2 + (- i ) , 2 i = ( - i ) a 3 + ( - i ) a 2
a = - 1 + i , л = { 0,1 }	12 = 1, - 1 = 1 ^a 4 + 1 ^a 3 + 1 ^a 2 + 1, 2 = 1 ^a 3 + 1 ^a 2

От редуцированного (mod p ) кольца Z p ( i ) потребуем, чтобы элемент (–1) являлся квадратичным вычетом (mod p ). Хорошо известно (например, [17]), что это условие выполняется для всех простых чисел вида p = 4 k + 1 (так называемых «пифагоровых простых»):

5,13,17,29,37,41,53,61,73,89,97,101,109, ^ ,

Так как возможная длина N преобразования (1) связана c (mod p ) соотношением делимости N | ( p – 1), то для p = 13 возможные длины преобразований N = 2,3,4, 6,12, причём элемент a = 4 имеет мультипликативный порядок, равный 12.

Заметим, что в отличие от классических систем счисления в кольце целых рациональных чисел Z один и тот же элемент кольца классов вычетов (mod p ) может иметь несколько (бинарных) представлений в системе счисления с основанием a .

Пример 2. Пусть p = 5, i = 2 (mod5), a = -1 -i = 2 (mod5),Л = {0,1}.

Свяжем с элементом кольца S p ( i ) его код – вектор цифр:

x = x ₀ a ⁰ + x 1 a 1 + x ₂ a ² + ... ^ ( x 0 , x 1 , x ₂,... ) .

Тогда при выбранных выше параметрах имеем:

0 o ( 0,0,0 ) о ( 1,0,1 ) ,

• 1    о ( 1,0,0, ) o ( 0,1,1 ) ,

• 2    o ( 0,1,0 ) ^ ( 1,1,1 ) ,

• 3    ^ ( 1,1,0 ) ,

• 4    o ( 0,0,1 ) .

то есть членов последовательности А00144 по классификации [18].

В этом случае «редуцированная» (mod p ) табл. 1 получается формальной заменой основания системы счисления и «цифр» на соответствующие элементы, а именно образы при каноническом отображении редукции Z( i ) ^ Z p ( i ) (« приведение (mod p ) » ) .

Пример 1 . Пусть p = 13, n — решение сравнения П 2 ^ -1 ^ p - 1(mod p ).

В рассматриваемом случае указанное сравнение имеет два решения n + = 5, П - = 8(mod 13).

Далее, при

П = 5(mod13), Л={0,i} ={0,5}, a = -1 + i = -1 + 5 = 4(mod13).

Случай поля Z _p ( i V2) = F p . Как показано в работе [14], в кольце целых квадратичных чисел Z ( i 2) существуют ровно четыре бинарные квазиканонические системы счисления: системы счисления с основаниями a = ± i V2 и множествами цифр Л ⁺ = {0,1}, Л {0,-1}.

Так как требуется, чтобы в редуцированном (mod p ) кольце элемент (–2) был квадратичным вычетом (mod p ), то, вычисляя символ Лежандра [17],

-2

-1

p

p

p

p -1/

= ( - 1) ^/2

■(-1)

- 1

нетрудно убедиться, правая часть последнего равенства равна (+1) при всех простых p с условием p2 + 4p - 5 ^ 0(mod16),

соответствующие соотношения правого столбца табл. 1 примут вид:

5² = 5 ■ 4¹ + 5 ■ 4⁰

8 = 5 ■ 4⁴ + 5 ■ 4³ + 5 ■ 4² + 5 ■ 4 0

2 ■ 5 = 5 ■ 4³ + 5 ■ 4²

( mod13 ) .

Отметим, что в соотношениях (8) коэффициенты 5 ^ i (mod 13) при реализации операций играют не роль чисел, а являются исключительно идентификаторами состояния соответствующего триггера.

что, очевидно, выполняется для простых вида p = 8 k + 1 или p = 8 k + 3, k e Z , то есть для простых чисел - членов последовательности A004625 и членов последовательности A007520 по классификации энциклопедии [18].

Пример 3. Пусть p = 11, n — решение сравнения П 2 ^ -2 ^ p - 2(mod p ).

В рассматриваемом случае указанное сравнение имеет два решения n ₊ ^ 3, П - = 8(mod 11).

Далее, при

П ^ 3 (mod11), Л = {0,1}, a = i ^ = 3( mod11)

соответствующие соотношения правого столбца табл. 2 примут вид:

10 2 = 1

- 1 = 10 = 1 -а ² + 1

2 = 1 -а ⁴ + 1 -а ² = 1 - 81 + 1 - 9

- ( mod11 ) .

Табл. 2. Арифметические операции в квазиканонических системах счисления кольца целых квадратичных Z ( i 2)

Система счисления { а , Л }	Преобразование выражений, возникающих при реализации арифметических операций
{ i V2, { 0,1 } }	12 = 1, - 1 = 1 -а 2 + 1, 2 = 1 -а 4 + 1 -а 2
{ i V2, { 0, - 1 } }	( - 1 ) 2 = 1, 1 = ( - 1) -а 2 + ( - 1), 2 = ( - 1) -а 2

Случай поля Z p ( i VX) = F p . Так как (—7) = 1(mod4), то Z ( i V7 ) = | a ⁺ 2^ ; a , b е Z ; a = b (mod2) | .

Тем не менее, для определения множества простых, для которых существуют редуцированные бинарные системы счисления, удовлетворяющие требованию (a), определим простые, для которых число (–7) является квадратичным вычетом (mod p ).

Вычисляя символ Лежандра с использованием квадратичного закона взаимности, имеем p-y

I —1 = 1 — II -I = (-1) /2 -I - I =I pJ I p JIp J Ip J

=(-1) p -x (_n м p -x )f p ъг p j ( )           17 j 17 j .

Нетрудно видеть, что квадратичными вычетами (mod 7) являются элементы 1,2,4(mod 7).

Таким образом, при p = 1,2,4(mod 7) справедливо соотношение Z _p ( i V7) = F _p и в поле F _p существуют бинарные системы счисления – редукции (mod p ) ква-зиканонических систем счисления в Z ( i 7) .

Табл. 3. Арифметические операции в квазиканонических системах счисления кольца целых квадратичных Z ( i 7)

Система счисления { а , Л }	Преобразование выражений, возникающих при реализации арифметических операций
{-Y^ , { 0,1 ) }	12 = 1, - 1 = 1 -а + 1 - а + 1 2 = 1 -а 3 + 1 -а
{-Ц^ , { 0, - 1 !	2 = ( - 1 ) а 3 + ( - 1 ) а , 1 = ( - 1 ) а 2 + ( - 1 ) а + ( - 1 )

Пример 4. Пусть p = 11, n — решение сравнения П 2 ^ -7 ^ p - 7(mod p ).

В рассматриваемом случае указанное сравнение имеет два решения n ₊ ^ 2, n _- ^ 9(mod 11). Далее, при

П ^ 2 (mod11), Л = {0,1}, 2-1 ^ 6 (mod11), а = 2-1 (-1 - i 41 ) = 7 (mod11), соответствующие соотношения правого столбца табл. 3 примут вид:

2 = 1-а3 + 1-а= 1-63 +1-6            1

!- (mod11).

• -1 = 1-а2 + 1-а +1 = 1-62 +1-6 +1-60

Таким образом, суммируя полученные результаты о полях Z p ( i4d ) при d = 1, 2, 7, получаем основное утверждение работы.

Утверждение . Для любого простого p существует по крайней мере одна из бинарных редуцированных систем счисления в Z p .

Заключение

Отметим, что сфера приложения рассматриваемого подхода, по мнению автора, не ограничивается приложениями к вычислению теоретико-числовых преобразований для их последующего использования в алгоритмах умножения больших целых чисел, при решении криптографических задач и т.п.

Действительно, реальные вычисления при численном решении любой прикладной задачи производятся не над полями действительных или комплексных чисел, а над некоторым множеством их рациональных аппроксимаций, причем происхождение обрабатываемых данных и возможности используемых вычислительных средств выделяют во множестве рациональных чисел конечное подмножество – некую «рабочую зону». После соответствующего масштабирования элементы этого множества можно считать целыми числами и, более того, вычетами по достаточно большому модулю [19].

Таким образом, рассмотренные «экзотические» системы счисления – бинарные редуцированные системы счисления в определенной мере представляют альтернативу традиционной «битовой» системе счисления.

Отметим также, что разработанная методика применима не только для построения бинарных редуцированных систем. Вопрос о целесообразности таких исследований с ориентацией на приложения зависит от характеристик существующих или перспективных вычислительных устройств.

По крайней мере, представляются интересными и реалистичными исследования тернарных редуцированных систем счисления, например, с «уравновешенным» цифровым алфавитом Л = {-1,0,1}, или каких-либо иных с возможностью простых реализаций базовых арифметических операций.

Работа выполнена при поддержке РФФИ (проект №16-41-630676_р_а) и в рамках госзадания по теме № 0026-2018-0106.