предложены Дж. М. Поллардом (J. М. Pollard), Math. Сотр. 25 (1971), 365-374. Чтобы понять значимость их вклада в решение проблемы, рассмотрим для начала механизм быстрого преобразования Фурье. Для данной последовательности К = 2 комплексных чисел {щ,... ,uj(-i) и данного комплексного числа

и = ехр{2пг/К) (37)

последовательность {щ,..., uk-i), определенная выражением (35), может быть быстро вычислена по следующей схеме. (Параметры Sj и tj в этих формулах равны либо О, либо 1, так что на каждый "проход" приходится 2* элементарных вычислительных операций.)

Проход 0. Пусть A°Цtk-l,..., to) = щ, где t = {tk-i... «0)2-Проход 1. Присвоить [4(Sfc i,tfc 2,...,to)

ли (О, tk-2, ...,to) + 2-»*-мт{1, tk-2,to).

Проход 2. Присвоить A\sk-l,Sk-2,tk-3, ,to) <-

AW{sk-i, о, tk-3, ...,to)+ 2-(»-2»-0m[i1 {Sk-u 1, tk-3,to).

Проход fc. Присвоить {Sk-l, . . . ,Si,So) <-

[*-il(sfc i,... ,si,0) +ш(-->Ьл[*-Ч(5* 1,... 1). По индукции очень просто доказать, что

Aksk-i,...,Sk-j,tk-j-u...,to)= е 2-i(». ,,..». ,b(t.-i...t.-,b„ (38) где t = (tk-i . tito)2, так что

W(.Sfc i,...,Si,so) = Us, где s- {soSi...Sk-i)2. (39)

(Важно отметить, что двоичные цифры числа s в конечном результате (39) обращены. В разделе 4.6.4 приводится дальнейший анализ такого рода преобразований.)

Прежде чем приступить к поиску обратного преобразования Фурье (uo,... ...,uj(i) по значениям {щ,... ,uk-i), заметим, что "двойное преобразование" имеет вид

0<«<А- 0<s,t<A

= е е "") ="(-г)шоак, (40)

так как для j, кратных К, сумма геометрической прогрессии Yjfj<e<k равна нулю. Поэтому обратное преобразование может быть получено точно так, как и прямое, за исключением того, что конечный результат делится на /Г и немного сдвинут. Возвращаясь к проблеме умножения целых чисел, предположим, что нужно вычислить произведение двух п-битовых целых чисел и и г». Будем оперировать (как и в алгоритме Т) группами битов. Положим

2n<2*z<4n, а: = 2*, 1 = 2 (41)

и запишем

u = (Uk-i...U,Uo)l, v = {Vk-i...ViVo)l, (42)

полагая числа и и v /Г-разрадными числами по основанию L, так что каждый из разрядов Uj или Vj есть /-битовое целое число. Поскольку 2*~/ > п, ведущие разряды в Uj и Vj для всех j > К/2 равны нулю. Соответствующие значения для к и I будут выбраны позже, когда в процессе решения задачи прояснится общая ситуация и можно будет при выборе к и I учесть всю имеюшуюся информацию.

Следующим шагом в процедуре умножения является вычисление преобразований Фурье (йо,..., uk-i) и (Йо, ..., vk-i) последовательностей {щ,..., uj-i) и (vq, ... ,Vf(-i), где по определению

utUt/2+, vt = Vt/2+. (43)

Для удобства масштабирование выполнено так, что любые щ и vt меньше 2~*, а это, в свою очередь, обеспечивает то, что абсолютные значения \й,\ и \vs\ оказываются меньше 1 для всех s.

Здесь возникает очевидная проблема, связанная с тем, что комплексное число UI не может быть точно представлено в двоичной системе счисления. Как же вычислить достоверное преобразование Фурье? Провидению было угодно, чтобы результат получился правильным даже в случае, если в процессе вычислений предъявить весьма скромные требования к точности представления чисел. Оставим на время эту проблему и предположим, что вычисления выполняются с бесконечной точностью. Анализ необходимой точности будет приведен несколько ниже (через пару страниц).

Для полученных й, и положим Ws = йУя {О < S < К) и определим обратное преобразование Фурье (wq, .. .,wk-i)- Как было разъяснено выше, получим

«+j=r i+j=r

так что целые числа Wr = 22*+ являются коэффициентами искомого произведения

u-v = Wk-2L~ + --- + WiL + Wo. (44)

Поскольку о < Wr < {г + 1)L < KL, каждое Wr содержит не более к + 21 бит, поэтому нетрудно получить двоичное представление для известных величин Wk, если только к не слишком велико по сравнению с I. Например, пусть нужно умножить и = 1234 на г; = 2341 при А; = 3 и / = 4. Вычисление изображения (йо,..., щ) по оригиналу и выполняется следующим образом (см. (12)).

Здесь a = 2-ь4г, /3 = 13u> и w = {l+i)/\/2. Это дает нам колонку ug в табл. 1. Данные в колонке Vg получаются из v аналогично. После этого находим Wg, умножив йд на Vg. Выполняем еще одно преобразование, учитывая соотношение (40), и получаем Ws и Wg. Итак, мы получили свертку (19), но на этот раз используя комплексные

Таблица 1

умножение при помощи дискретного преобразования фурье

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

Попробуем теперь оценить время, необходимое этому методу при больших числах, если использовать т-битовую арифметику в формате с фиксированной точкой. Из упр. 10 видно, что в процессе преобразования все величины А будут меньше 1 из-за масштабирования (43). Следовательно, достаточно иметь дело только с дробными т-битовыми частями (.a i... a m)2 для действительной и мнимой частей любых промежуточных результатов. Так как входные величины щ и vt являются действительными числами, можно упростить вычислительную процедуру, а именно - вместо 2К действительных значений на каждом шаге преобразований использовать только К значений (см. упр. 4.6.4-14). Чтобы не усложнять выкладки, далее эти тонкости учитывать не будем.

Прежде всего необходимо вычислить ш и ее степени. Для простоты сформируем таблицу значений ..., и>~. Положим

ojr = ехр(27гг72) (45)

таким, что uii = -1, W2 = г, и>з = (1 + i)/\/2, и>к = oj. Если uir = Хг + гуг, то имеем uir+i = Xr+i + гуг+i, где

l + Xr Уг

-i = V- - = 2-

[См. S. R. Tate, IEEE ЪansactioDS SP-43 (1995), 1709-1711.] На вычисление ал, и>2, . ,и>к затрачивается по сравнению с остальными операциями относительно немного времени, так что вполне можно использовать любой стандартный способ извлечения квадратных корней. После uir можно легко вычислить все степени oj, учитывая, что

= uil" . ..ujI ujI°, если j = {jk-i • jijo)2- (47)

Поскольку каждое значение oj получается как результат умножения и>г не более чем к раз, ошибки вычислений при таком методе не накапливаются. Общее время вычисления всех значений oj равно 0{КМ), где М - время выполнения операций умножения т-битовых комплексных чисел, поскольку на вычисление каждого из следующих значений по известному предыдущему требуется одна операция умножения. На выполнение последующих операций необходимо больше циклов, чем 0{КМ), поэтому на вычисление степеней w требуется сравнительно мало времени.