11.2 Алгоритмы ТЧП по основанию l по модулю простых чисел Мерсенна

В работе [5] Рид и Троунг определили теоретико-числовое преобразование по модулю простых чисел Мерсенна в поле Пара преобразований ТЧП в имеет вид

где простое Мерсеннар т.е. являются элементами вида где

а — образующий элемент мультиплакативной подгруппы состоящей из элементов

Очевидно, что отсюда Следовательно, размерность ТЧП-М можно выбрать равной

D определено явное выражение для образующего элемента а степени Пусть тогда

Нуссбаумер предложил конструкцию ТЧП-М в не требующего нетривиальных умножений. Пара ТЧП в этом случае имеет вид

где

Из (11.20) следует, что элемент равный является образующим элементом мультипликативной подгруппы Отсюда, если в (11.18) выбирать размерность преобразования и образующий элемент а такой, что то среди множества удовлетворяющих данному условию, целесообразно выбрать такое а, чтобы тогда умножение на элементы целое) требуют только операций сложения и сдвигов на степени двойки.

Как и в предыдущем разделе, для ТЧП-М могут быть синтезированы быстрые алгоритмы по основанию 2 четырех различных типов. Остановимся подробнее на синтезе алгоритмов ТЧП-М по основанию 8. Матричное выражение для такого алгоритма имеет вид

где не требует операций умножения, определено в (11.19)).

Для вычисления каждого блока в (11.21) требуется 52 вещественных сложения и два умножения на степени двойки. Кроме того, умножение на требует трех вещественных умножений и трех вещественных сложений. Отсюда общее число вещественных арифметических операций для (11.21) равно