33-1 Двоичный алгоритм вычисления наибольшего общего делителя.

Современные компьютеры выполняют операции сложения и вычитания, а также проверяют чётность числа быстрее, чем выполняют деление с остатком. Поэтому интересен двоичный алгоритм вычисления наибольшего общего делителя (binary gcd algorithm), избегающий деления с остатком.

a.Докажите, что gcd(a,6) = 2gcd(a/2,6/2) для чётных целых чисел а и Ь.

b.Докажите, что если а четно, а Ь нечётно, то gcd(a,6) = gcd(a,6/2).

c.Докажите, что если оба числа а и Ь нечётны, то gcd(a,6) =

d. Постройте алгоритм, вычисляющий gcd(a,6) с использованием указанных соотношений за время 0(lg(max(a, Ъ))) (считая, что вычитание, проверка на чётность, удвоение и и деление пополам выполняются за единицу времени).

33-2 Оценка числа битовых операций в алгоритме Евклида.

a.Покажите, что обычный способ деления уголком числа а на число Ь требует 0((1 + lg q) lg 6) битовых операций операций (q - частное).

b.Положим p(a,b) = (1 + lga)(l + lg6). Докажите, что число битовых операций в процедуре Euclid, требуемых для сведения задачи вычисления gcd(a,6) к задаче вычисления gcd(6, a mod b), не превосходит с(р(а,Ь) - ц(b, a mod b), если с > 0 - достаточно большая константа. (Используйте оценку предыдущего пункта.)

c.Докажите, что процедура Euclid (а, Ъ) выполняет не более 0(р(а,Ь)) битовых операций. Докажите, что процедура Euclid, применённая к двум /3-битовым числам, выполняет не более 0([32) битовых операций.

33-3 Три алгоритма вычисления чисел Фибоначчи.

В этой задачи мы сравниваем три способа вычисления га-го числа Фибоначчи Fn при заданном га. (Для простоты мы считаем, что операции сложения, вычитания или умножения выполняются за единичное время независимо от размера чисел.)

a.Докажите, что время работы простейшей рекурсивной процедуры, непосредственно реализующей формулу (2.14), экспоненциально зависит от га.

b.Покажите, как техника запоминания промежуточных результатов позволяет сократить время до О (га).

c.Покажите, как вычислить Fn за время О (lgra), используя только операции (сложение и умножение) с целыми числами. (Указание. Рассмотрите матрицу

gcd((a-6)/2,6).

и её степени.)

d. Оцените время работы трёх описанных алгоритмов, исходя из более реалистичных оценок времени сложения и умножения: считайте, что сложение двух /3-битовых чисел требует времени 0(/3), а умножение - 0(/32).

33-4 Квадратичные вычеты.

Пусть р - нечётное простое число. Элемент а £ Z* называется квадратичным вычетом (quadratic residue), если существует х £ Z*, для которого х2 = a (mod р).

a.Докажите, что в группе Z* имеется в точности (р - 1)/2 квадратичных вычетов.

b.Пусть р - простое и а £ Z*. Символ Лежандра (Legendre

>ol), обозначаемый (-), определяется так: (-) = 1, если а

является квадратичным вычетом в Z*, и yj = -1 в противном случае. Докажите, что

Предложите эффективный алгоритм, определяющий, является ли заданный элемент а £ Z* квадратичным вычетом. Оцените время его работы.

c.Пусть простое число р имеет вид Ак + 3, а число а £ Z* является квадратичным вычетом. Докажите, что ak+1 mod р является квадратным корнем из а по модулю р. За какое время можно вычислить квадратный корень по модулю р из квадратичного вычета а £ Z*, если р имеет вид Ак + 3?

d.Предложите эффективный вероятностный алгоритм поиска (для любого простого р) элементов а £ Z*, не являющихся квадратичными вычетами. Сколько арифметических операций будет выполнять в среднем этот алгоритм?

Замечания.

Книга Нивена и Цукермана [191] - превосходный учебник по элементарной теории чисел. В книге Кнута [122] детально рассматриваются алгоритмы нахождения наибольшего общего делителя и другие базовые алгоритмы теории чисел. Из книг Ризеля [168] и Баха [16] можно узнать о современном состоянии вычислительной теории чисел. Задачи разложения на множители и проверки на простоту рассматриваются в книге Диксона [56]. В сборнике под редакцией Померанца [159] можно найти несколько хороших обзоров статей.

Кнут в [122] обсуждает просхождение алгоритма Евклида. Он содержится в седьмой книге знаменитых «Начал» Евклида (предложения 1 и 2), написанной около 300 г. до Р.Х. Возможно, идея алгоритма восходит к трудам Евдокса (около 375 г. до Р.Х.). Ал-

горитм Евклида претендует на роль древнейшего нетривиального алгоритма - соперничать с ним может только так наываемый «русский народный алгоритм умножения чсиел» (глава 29), который был известен ещё древним египтянам.

Кнут отмечает, что частный случай «китайской теоремы об остатках» был известен китайскому математику Сун-Цу, жившему где-то между 200 г. до Р.Х. и 200 г. от Р.Х. Тот же самый частный случай был разобран древнегреческим математиком Ни-комахом около 100 г. от Р.Х. Более общую форму теореме придал Чин Чью-Шао в 1247 году. В полной общности теорема была сформулирована и доказана Леонардом Эйлером в 1734 году.

Вероятностный алгоритм проверки чисел на простоту, рассмотренный нами, предложен Миллером [147] и Рабином [166]; он является (с точностью до постоянного множителя) самым быстрым из известных, Доказательство Теоремы 33.39, приведённое нами, следует идее Баха [15]. Более сильный результат о тесте Миллера - Рабина доказан Монье [148,149]. Использование случайности тут существенно - наилучший известный детерминированный (не использующий датчика случайных чисел) алгоритм проверки на простоту известен как версия Коэна - Ленстры [45] теста Адлемана, Померанца и Румели [3]. На проверку простоты числа п он тратит время (lgn)°(lglglgn) (чуть больше полиномиального).

Задача поиска большого «случайного» простого числа подробно обсуждют Бошемин, Брассар, Крепо, Готье и Померанц [20].

Идея криптосистемы с открытым ключом принадлежит Диффи и Хеллману [54]. Криптосистему RSA предложили в 1977 году Ривест, Шамир и Адлеман. С тех пор криптография стала быстро развивающейся областью со множеством интересных результатов. Например, Гольдвассер и Микэли [86], показали, как можно использовать рандомизацию (датчик случайных чисел) для построения криптосистем с открытым ключом вероятностные алгоритмы. Гольдвассер, Микэли и Ривест [87] предложили схему электронной подписи, взлом которой по трудности равносилен разложению чисел на множители. Гольдвассер, Микэли и Раков [87] ввели класс так называемых систем с нулевым разглашением, про которые можно доказать (при некоторых естественных допущениях), что ни одна из сторон не узнаёт больше, чем ей положено.

Метод разложения чисел, называемый /-эвристикой, впервые был предложен Поллардом [156]. Вариант, излагаемый нами, предложил Брент [35].

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