Рис. 33.1 33.1: Работа процедуры EXTENDED-EUCLID на входе (99,78). EXTENDED-EUCLID(99,78) возвращает тройку (3,-11,14), так что НОД(99, 78) = 3 = 99 • (-11) + 78 • 14.

вычисление Euclid (-Ffc+i, Fk) включает ровно к - 1 рекурсивных вызовов и верхняя оценка достигается.

Поскольку Fk примерно равно tpk/\/5, где <р = (1 + у/5)/2 - так называемое «золотое сечение» см. (2.14)), число рекурсивных вызовов для Euclid (а, 6) (при а > 6 0) составляет O(lgb). (Более точную оценку см. в упр. 33.2-5.) Если процедура Euclid применяется к двум /3-битовым числам, то ей приходится выполнять 0(/3) арифметических операций, или 0(/33) битовых (считаем, что умножение и деление /3-битовых чисел требует 0(/32) битовых операций). На самом деле справедлива более сильная оценка 0(/32) на число битовых операций, выполняемых процедурой Euclid (задача 33-2).

Расширенный алгоритм Евклида.

Немного дополнив алгоритм Евклида, можно получать с его помощью коэффициенты хну, для которых

(теорема 33.2). Обратите внимание, что коэффициенты хну могут оказаться не только положительными, но и нулевыми или отрицательными. (Эти коэффициенты нужны для вычисления обратных элементов в кольце вычетов.)

Процедура Extended-Euclid получает на вход произвольную пару целых чисел и выдаёт на выходе тройку целых чисел (d, х,у), удовлетворяющих соотношению (33.18).

Extended-Euclid (a,b)

1if b=0

2then return (a,1,0)

3(d,x,y) \gets Extended-Euclid(b,a mod b)

4(d,x,y) \gets (d, y, x-\lfloor a/b\rfloor y)

5return (d,x,y)

Рисунок 33.1 иллюстрирует работу процедуры Extended-Euclid на входе (99, 78)

Если 6 = 0, процедура Extended-Euclid выдаёт значение d = а, а также значения х = 1 и у = 0, для которых d = а = ах + by.

Если 6/0, рекурсивный вызов позволяет найти числа (d!, х, у), таких, что d = НОД(Ь, a mod 6) и

Как мы знаем, d = d, так что осталось найти хну, для которых d = ахЛ-Ьу. Перепишем равенство (33.19): d = 6ж+ (a - [a/b\b)y! =

(33.19)

ау + Ь(х - [а/Ь\у). Таким образом, можно положить ж = у и у = х - [а/Ь\у.

Как и раньше, число рекурсивных вызовов при работе Extended-Euclid (а, Ь) составляет O(lgb). Упражнения 33.2-1

Объясните, каким образом из равенств (33.13)-(33.14) следует равенство (33.15). 33.2-2

Проследите за выполнением процедуры Extended-Euclid на входе (899,493) и найдите тройку (d,x,y). 33.2-3

Докажите, что для любых целых чисел а, к и п выполняется равенство gcd(a, п) = gcd(a + кп, п). 33.2-4

Перепишите процедуру Euclid, заменив рекурсию циклом и ограничившись фиксированным объёмом памяти (используя лишь фиксированное число целых переменных)

33.2-5

Пусть a > Ь 0. Покажите, что процедура Euclid (а, Ъ) выполняет не более l+logv Ь рекурсивных вызовов. Докажите более точную оценку 1 + logv(6/gcd(a, Ъ)).

33.2-6

Какой ответ даёт процедура Extended-Euclid (Д+1, Fk)l 33.2-7

Докажите, что если d \ a, d\bnd=ax-\- by, то d = gcd(a, b). 33.2-8

Распространим определение функции gcd на большее число аргументов, положив gcd (ао, а\,... , ап) = gcd(ao, gcd(ai,... , ап)). Покажите, что результат не зависит от порядка аргументов. Предложите алгоритм нахождения коэффициентов жо, х\,... , хп, для которых gcd(ao, а\,... , ап) = аоХо + а\Х\ + • • • + апхп,, выполняющий 0(п + lg(max8- си)) операций деления.

33.2-9

Назовём наименьшим общим кратным (least common multiple) целых чисел а\, а2, ,ап наименьшее положительное целое число, кратное каждому из них (обозначение 1ст(ао, а\,... , ап)). Укажите эффективный алгоритм, вычисляющий 1cm(ао, а\,... , ап) и использующий операцию поиска наибольшего общего делителя (двух чисел) в качестве подпрограммы.

33.2-10

Докажите, что числа щ, п2, п% и п4 попарно взаимно просты тогда и только тогда, когда gcd(raira2, П3П4) = gcd(raira3, п2пЛ = 1.

Покажите, что это утверждение можно обобщить, доказать утверждение такого типа: числа п\,п2,... ,пк попарно взаимно просты, если и только если gcd(ai,&i) = gcd(a2,&2) = ••• =

gcd(ai,6i) = 1, где t = \\gk], а числа аг- и Ьг- представляют собой произведения некоторых гаг-.

33.3. Модулярная арифметика

Арифметические операции по модулю га проводятся над числами 0,1,... , га - 1 так: если результат сложения, вычитания или умножения выходит за пределы указанного интервала, то он заменяется остатком при делении на га. Сложнее обстоит дело с делением. Чтобы разобраться в этом, напомним некоторые понятия теории групп.

Конечные группы.

Множество S с определённой на нём бинарной операцией © называется группой (group), если выполнены такие свойства:

1.Замкнутость (closure): а ф Ь £ S для любых a,b £ S.

2.Существование нейтрального элемента (identity): существует элемент е £ S, для которого ефа = афе = а для любого а £ S (такой элемент может быть только один, так как е = е е = е для любых двух элементов е и е с таким свойством).

3.Ассоциативность (associativity): а © (Ь © с) = (а ф Ъ) ф с для любых а, 6, с £ S*.

4.Существование обратных элементов (inverses): для всякого а £ S* найдётся единственный элемент Ь £ S, для которого а ф Ь = Ь ф а = е.

Например, целые числа с операцией сложения: образуют группу. В ней 0 служит нейтральным элементом, а обратным (по сложению) элементом к числу а является число ( - а). Группа называется абелевой (abelian), если выполнено свойство коммутативности: а ф Ь = Ь ф а для всех a,b £ S.

Группа называется конечной (finite), если число элементов в ней конечно.

Аддитивные и мультипликативные группы вычетов Можно построить две группы, элементами которых будут вычеты (остатки по модулю га, или классы эквивалентности по модулю га, см. раздел 33.1).

Мы складываем и умножаем вычеты по модулю га по правилам

Нп +п [Ь]п = [а+ Ь]п, [а]п -п [b]n = [ab]n.

Эти определения корректны, так как сумма (произведение) не изменится по модулю га, если изменить слагаемые (множители) на эквивалентные по модулю га.

Аддитивная группа вычетов по модулю га (additive group modulo п) содержит вычеты [0]„, [1]„,... , [га - 1]п; они складываются описанным выше образом; она обозначается (Zra,+ra).