1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 59
Текст из файла (страница 59)
Пусть Ȅ— кольцо вычетов ио модулю т. Тогда в кольце П элемент и имеет обратный ('ио модулю т) и ш — примитивный корень и-й степени из единицы. Доказательство. Так как п — степень числа 2, а т нечетно, то т и п взаимно просты. Поэтому и имеет обратный по модулю т '). Так как о!чь1, то ш«= ш«/з ш "/' =— ( — 1)( — 1) = ') Вто утверждение составляет одну из основных теорем теории чисел. В равд, 8.8 будет показано, что если и и Ь взаимно просты, то существуют такие целые чясла х и у, что ох+Ьу=1. Тогда пх 1 (шов Ь). Полагая Ь=ш и о=п, получаем наше утверждение.
гл. з. выстгоа пэеовглзованив еуэьв =1(шод(ьзтз+1)). Тогда из леммы 7.5 следует, что ьз — примитивный корень п-й степени из единицы в Я . П Теорема 7.5 важна потому, что теорема о свертке верна для кольца целых чисел по модулю 2тз+1. Если надо вычислить свертку двух п-мерных векторов с целыми компонентами, причем компоненты свертки заключены между 0 и 2чз, мы можем быть уверены, что ответ будет точным.
Если же компоненты свертки не заключены между 0 и 2т', то они точны по модулю 2"~' +1. Сейчас мы уже почти готовы к тому, чтобы установить, сколько требуется битовых операций для вычисления свертки по модулю т. Сначала, однако, выясним, сколько битовых операций требуется для вычисления вычета целого числа по модулю т, так как это существенный шаг в подсчете числа битовых операций на основе числа арифметических операций по модулю т. Пусть т=иг+1 для некоторого целого числа р.
Для вычисления а по модулю т применим обобщение приема "отбрасывания девяток" (нахождения вычета по модулю 9). Если число а разложено по основанию ьзг, т. е. записано в виде последовательности из! блоков по р цифр в каждом, то а по модулю т можно сосчитать, попеременно складывая и вычитая эти 1 блоков из р цифр. 1-! Лемма 7.6. Пусть т=аг+! и а='Яа~ьзг', где 0(а;ч..ьзг для г=о каждого 1. Тогда 1-1 а= Ха,( — 1)'(шобт). з=ь Д о к а з а т е л ь с т в о.
Достаточно увидеть, что ьзг = иа — 1 (шоп т). П Заметим, что если число блоков ! в лемме 7.6 фиксировано, то вычет числа а по модулю т можно найти за Оз(р [он ьз) битовых операций. Пример 7.3. Пусть п=4, ьз=2 и т=2'+!. Тогда, применяя лемму 7.6, положим р=2. Рассмотрим число а, запись которого по основанию 2 имеет вид 101100. В нашем случае а,=00, а,=11 и а,=10. Вычисляем а, — а,+а,= — 1, а затем, прибавляя т, находим, что а=4(пюб 5). Так как а=44, то результат верен. П Лемма 7.6 дает эффективный метод вычисления а по модулю т. Она играет важную роль в следующей теореме, устанавливающей верхнюю границу на число битовых операций, требуемых для вычисления дискретного преобразования Фурье и обратного к нему. Теорема 7.6. Пусть ьз и п — степени числа 2 и т=ьзыз+1.
Пусть [а„а„..., а„,!г — вектор с целочисленными компонентами, гдг Ж:а,(т для каждого ~'. Тогда дискретное преобразование Фурье т.з. ВпФ пРи испОльзОВАНии БитоВых ОпеРАциЙ для !а„а„..., а„т!г и обратное к нему можно вычислить по мо. дулю гп за Ов (п' 1оп и !оп «т) шагов. Д о к аз а тел ь ство. Применить алгоритм 7.1 или 7.2. Для обратного преобразования подставить от-' вместо оз и умножить каждый результат на и-'. Целое число по модулю т можно представить цепочкой из Ь= ((и/2) 1оя от)+! символов 0 и 1. Так как т=2ь-'+1, то вычеты по модулю т можно представить в виде двоичных чисел от 00...0 до 100...0.
В алгоритме 7.1 участвует сложение целых чисел по модулю т и умножение по модулю т целого числа на степень числаго, Эти операции выполняются за время О(п !Оп и). В силу леммы 7.6 сложение по модулю т занимает ОБ (Ь) шагов, где Ь= ((и/2) 1оп от)+1. Умножение на ьтг, 0(р и, эквивалентно сдвигу влево на р1оя ет разрядов, поскольку «т — степень числа 2. Получающееся целое число содержит не более ЗЬ вЂ” 2 разрядов, так что по лемме 7.6 сдвиг и последующее вычисление вычета занимают ОВ(Ь) шагов. Таким образом, прямое преобразование Фурье можно найти за время ОБ(Ьп !опп), или ОБ(п' !опп!Оя от), В обратном преобразовании участвует умножение на гэ-Р и П-т.
ТаК КаК ФРГЛе-Р=1 (ШОГ! т), таГВе Р И Р (ШОбт). СЛЕдазаТЕЛЬНО, ВМЕСТО уМНОжЕНИя На ГО-Р МОЖНО уМНОжатЬ На Ете-г, Чта эквивалентно сдвигу влево на (и — р) 1оп от разрядов, причем получающееся целое число содержит не более ЗЬ вЂ” 2 разрядов. Снова по лемме 7.6 вычеты можно найти за ОВ(Ь) шагов. Наконец, рассмотрим умножение на и-'. Если п=2", то оно сводится к сдвигу влево на и 1оп ет — й разрядов (в результате получается число не более чем с ЗЬ вЂ” 2 двоичными разрядами) и вычислению вычета по лемме 7.6. Таким образом, нахождение обратного преобразования Фурье также требует ОВ(п' !оп и 1оп в) шагов. П Пример 7.4. Пусть от=2, п=4 и т=б. Вычислим преобразование Фурье вектора !а„а„а„аз)г, где а, =1.
Так как а~(5 для каждого 1, то можно ожидать, что этот вектор можно будет восстановить, проведя вычисления по модулю т. Для представления чисел мы используем три бита, но в действительности у нас будут лишь 000,..., 100, если не считать промежуточных результатов. В соответствии с алгоритмом 7.1 мы должны вычислить коэффициенты, указанные на рис. 7.6, где вместо «т подставлено число 2. Рва У.б.
Вычвсаевве быстрого вреобразозаввя Фурье Аля В=4. Гл. е ВыстРОВ пРеОВРАВОВАние ФуРье Значения переменных и выражений на рис. 7,6 для нашего примера таковы: а,=000 а,=001 а,=0!0 а,=0!1 а,+а~ 010 а1+а, 100 а,+4а,=011 а,+4а,=011 Ь,=001 Ь,=011 Ь,=100 Ь,=010 Преобразованием вектора [О, 1,2,3)тбудет, таким образом, вектор [1, 4, 3, 2Р' по модулю 5. Рассмотрим последний элемент Ь, в нижней строке. Он вычисляется по двум последним элементам в средней строке: Берем а1+4аь 011 Сдвигаем на три разряда влево (умножаем на 8) 11000 Расщепляем на три блока по 2 разряда 1 1000 Складываем первый и третий блоки и вычитаем второй — 1 Прибавляем т=5 100 Прибавляем а,+4а,=011 111 Вычитаем т 010 Для нахождения обращения заметим, что 2-' — 8(пюб 5), 4-'= — 4 (пюб 5) и 8-'=— 2 (шоб 5).
Таким образом, формулы для обратного преобразования можно вывести из рис. 7.6, поменяв местами а1 и Ьп а также 2 и 8. Это вычисление выглядит так: Ь,=001 Ь,=100 Ь,=011 Ь,=0!0 Ьь+Ьь = 100 Ь1+ да = 001 Ьо+4Ьа = 011 Ь1+ 4Ьваив 010 4а, 000 4а, = 011 4а, = 100 4а, 010 Наконец, делим каждый ответ на 4 (умножаем на 4, ибо 4-'=- Ви 4 (шоб 5)), и получаем [О, 1, 2, 31г в качестве [а„а„а„а,!г. С) Следствие теоремы 7.6.
Пусгпь на вычисление произведения двух й-разрядных двоичных целых чисел тратится ОВ (М (й)) шагов. Пусть а и Ь будут и-мерными векторами длины по целочисленными компонентами между 0 и а', где и и в — степени числа 2. Тогда свертку а®Ь, а также положительно и отрицательно обернутые свертки векторов а и Ь по модулю в"+1 можно вычислить за время О в (МАХ [и' !ой и 1ой в, пМ (и 1ой а))), Первая величина здесь представляет время вычисления преобразований, а вторая — выполнения 2п умножений (и !ой в+1)- разрядных двоичных целых чисел. Наилучшее известное значение М (й) равно й 1ой й 1ой 1ой й (равд.
7.5). При этом значении вторая величина больше первой, так что для вычисления соответствующей свертки требуется ОВ (и' 1ой и !од 1ой п [ой в !ой 1ой в 1ой 1ой!ой ы) шагов. тл. пгоизведаннв полнномоа 7.4. ПРОИЗВЕДЕНИЕ ПОЛИНОМОВ Задача умножения двух полнномов от одной переменной по существу совпадает с задачей нахождения свертки двух последователь. настей, а именно л-1 « /л-! ~ Ол-т «-1 ~~~', а!х') ~~~.", Ь х/)- 2', с„х", где се= ~~.", а Ь, „.
! о п«о ь«о о Как и раньше, а„и Ь считаются нулями, если р(0 или р)п. Напомним, что коэффициент с,л, должен быть нулем. Поэтому имеем дополнительные следствия теоремы 7.4. Следствие 3 теоремы 7.4. Когффициенты произведения двух полиномов степени п можно вычислив!ь за Оа(п 1ой п) шагов. Д о к аз а тел ь от в о. В силу следствия 1 теоремы 7.4 и соображений, приведенных выше. П Следствие 4 теоремы 7.4. Допуслшм, что произведение двух й-разрядных двоичных целых чисел можно вычислшпь ва М(й) исагав. Пусть л-1 л-! р (х) «л ~ а!х1, о (х)лл ~ Ь х!, ! о ! о где а, и Ь! — целые числа между 0 и ил!11)Г и для всех 1 и ), а и и гав степени числа 2. Тогда коэффициента полинома р(х)4(х) можно вычислить за Оз (МАХ[п'. 1ой и 1ой !о, пМ (и 1ой !о))) шагав.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
