С.А. Абрамов - Вычислительная сложность алгоритмов, страница 8

Для доказательства достаточно положить a0 = Fn ; a1 = Fn −1 , изатраты алгоритма будут примерно равны log 22 a0 , т.к. для чисел Фибоначчи каким бы не былалгоритм деления, он будет эквивалентен вычитанию.Более того, можно доказать теорему о нижней границе класса алгоритмов Евклида(отличающихся алгоритмом деления) и показать, что она равна log 22 a0 .33Модулярная арифметика.Все вычисления производятся по модулю некоторого числа.Определение. Число a сравнимо с b по модулю k, если число k делит разность (a − b ) .Обозначение: a ≡ b(mod k ) .Утверждение.(i)Отношение сравнимости по модулю k является отношением эквивалентности.(ii) Если a1 ≡ b1 (mod k ) , a2 ≡ b2 (mod k ) , тоa1 + a2 ≡ b1 + b2 (mod k ) , a1 − a2 ≡ b1 − b2 (mod k ) , a1a2 ≡ b1b2 (mod k ) .(iii) Каждое число a сравнимо по модулю k с одним и только одним числом измножества {0, 1, ...

, k − 1} .Отношение эквивалентности разбивает множество целых чисел на непересекающиесяклассы, причём количество этих классов равно k. Возьмём по одному представителю изкаждого класса: {a0 , a1 , ... , ak −1} — полная система вычетов по модулю k. Система⎧⎢ k ⎥⎢ k ⎥⎫I = {0, 1, ... , k − 1} — каноническая система вычетов. S = ⎨⎢− ⎥, ... , − 1, 0, 1, ... , ⎢ ⎥ ⎬ —⎣ 2 ⎦⎭⎩⎣ 2 ⎦симметричная система вычетов. В курсе линейной алгебры доказывалось, что Z k являетсякольцом вычетов по модулю k. При этом вычеты называются изображениями. При сложениискладываем изображения, если остаёмся в рамках канонической системы, то всё в порядке,если получаем число ≥ k , то вычитаем k. Противоположный a элемент определяется какk − a . Поэтому для битовых затрат операций сложения и вычитания имеем оценку O(m) ,где m = ν (k ) .Если для умножения используем алгоритм «наивное» умножения, то затраты допускаютоценку O m 2 .( )Если k — простое, то Z k является полем, если k не является простым, то Z k — это кольцо сделителями нуля.Сосредоточимся на случае k = p — простое число.

Покажем, откуда следует существованиеобратного элемента. Рассмотрим каноническую систему вычетов: {0, 1, ... , p − 1} . Израсширенного алгоритма Евклида следует, что найдутся такие целые s и t, что будет верноsp + ta = 1 ⇔ ta ≡ 1(mod p) . Следовательно, t будет обратным к a. Но t является целым и,возможно, не входит в систему. Было показано, что t < p , и t может быть отрицательным.Поэтому, если t ≥ 0 , то всё в порядке и t входит в рассматриваемую систему вычетов. Еслиt < 0 , то прибавим p и попадём в рамки системы (ещё не более одной операции).

Затраты накаждом шаге расширенного алгоритма Евклида для перехода от si −1 к si и от ti −1 к tiсравнимы с затратами на деление с остатком. Но расширенный алгоритм Евклида позволяетвычислять только t и не тратить операции на вычисление s. Но для O log 2 p это не имеетзначения.()Пример. a = 5 , p = 132 ⋅ 13 + (−5) ⋅ 5 = 1 ⇒ для числа 5 обратным будет (−5) ⇒ добавим 13 и получим(−5) + 13 = 8 и имеет место сравнение 8 ⋅ 5 ≡ 1(mod 13) .34Как следует из расширенного алгоритма Евклида, обращать можно не только по простомумодулю, лишь бы a и p были взаимно простые.Теорема (малая теорема Ферма). Пусть p — простое, u — целое, u ≠ 0 ⇒ u p −1 ≡ 1(mod p) ,при условии, что p не делит u.Условие p — простое является существенным: Например, u = 5 , p = 6 ⇒ 55 ≡/ 1(mod 6) . Такчто расширенный алгоритм Евклида в этом плане лучше.Проблемой является распознавание простоты числа такое, чтоб его сложность былаполиноминально ограниченной: O m d , m = ν (n) или, что то же самое, O(log d n ) .

Можнопопробовать зацепиться за малую теорему Ферма: u p ≡ u (mod p) ⇒ p — простое. Т.е. можнодля возведения в степень воспользоваться бинарным алгоритмом возведения в степень, нодля сокращения затрат брать результат по модулю. Далее проверить условия теоремы и датьответ. Но такой алгоритм, вообще говоря, неверный, т.к.

существуют составные числаКармайкла (бесконечно много), которые не ловятся таким алгоритмом.( )Тем не менее, в 2002 году три индийских математика — Агравал, Кайал и Саксена —разработали алгоритм определения простоты числа с полиномиальной сложностью. Этоталгоритм базируется на следующем утверждении:Утверждение. Пусть u, n ∈ N , u ⊥ n (взаимно простые). Тогда n является простым, если итолько если (x − u ) ≡ x n − u (mod n) .nДоказательство. Необходимость.

Пусть n — простое и, для определённости, нечётное (дляn = 2 проверяется непосредственно). Сравним коэффициенты при степенях x k для 1 < k < n .В правой части очевидно все коэффициенты равны нулю, а в правой из формулы биномаНьютона получаем (−1) k Cnk a n − k . Т.к. для числа сочетаний верно Cnk ≡ 0(mod n) (см.

задачу42), то получаем, что (−1) k Cnk a n−k ≡ 0(mod n) , т.е. коэффициенты в левой и правой частисравнимы с нулём по модулю n. Для k = n доказывать нечего, проверим свободный член:надо показать, что (−u ) n ≡ −u (mod n) , но это следует непосредственно из малой теоремыФерма.Достаточность докажем от противного. Пусть n — составное, тогда найдётся такое q,которое будет являться делителем n. Рассмотрим ещё k такое, что q k ещё делит n, а q k +1 уженет. Рассмотрим число сочетаний из n по q:Cnq =n[(n − 1) ⋅ ...

⋅ (n − q + 1)]q!Ни один из множителей в квадратных скобках не может делиться на q. В итоге послесокращения должно получиться целое число, которое на q k уже не делится (т.к. одно q иззнаменателя сократится с n). q k ⊥ u n − q , и коэффициент в правой части (−1) n − q u n − qCnq x q несравним с нулём по модулю n, что противоречит утверждению. Полученное противоречиезавершает доказательство.Просто построить алгоритм определения простоты числа на основе доказанногоутверждения нельзя, но использовать его как основу вместо малой теоремы Ферма вполнереально.Итак, получаем следующий способ определения простоты числа: возьмём u = 1 , раскроемскобки и посчитаем остаток от деления на n. Но после раскрытия скобок получим n + 1слагаемое, и нужно будет поработать со всеми ими.

Откуда для сложности алгоритма будетверна оценка Ω(n ) , а n ≈ 2m и всё хорошо, но сложность экспоненциальная.35()Посмотрим, что предлагают авторы. Рассмотрим сравнение: (x − u ) ≡ x n − u mod x r − 1, n ,nкоторое означает следующее:делятся на n.(x − u )n()− x n + u = Q( x) x r − 1 + S ( x) и все коэффициентыЧтобы двигаться к полиномиальности, нужно чтобы r было маленьким. Возводить в степеньнадо бинарным алгоритмом возведения в степень, каждый раз беря результат по модулю.Во-первых, r берётся не «с потолка», а совершенно конкретным, допуская оценку r = O(m6 ) .Во-вторых, u тоже не является произвольным. Авторы показывают, что достаточнопроверить сравнительно небольшой набор, допускающий оценку O m r ~ m 4 . Тогда, еслииспользовать эти r и u, то по необходимому и достаточному условию можно распознатьпростоту числа, и сложность будет полиномиальной.(36)Об одном классе рекуррентных соотношений («разделяй ивластвуй»)Мы будем рассматривать рекурсивные алгоритмы.

Рекурсивные соотношения дляисследования сложности таких алгоритмов являются эффективным методом. Основой будутлинейные рекурренции с постоянными коэффициентами и, возможно, с правыми частями.Для начала рассмотрим «игрушечный» алгоритм построения множества Vn , содержащего всеположительные целые числа, десятичные записи которых таковы, что сумма их цифр равна n.V1 = {1} . Упростим задачу, рассматривая только такие цифры, десятичные записи которыхсостоят только из единиц и двоек: V2 = {11, 2} , V3 = {111, 21, 12} .

Задача ставится следующимобразом: дано n, и надо построить Vn .Множество Vn можно разделить на 2 непересекающихся подмножеств: на конце чиселпервого подмножества стоят единицы, на конце цифр второго — двойки. Если откинутьпоследнюю цифру, то получим Vn −1 и Vn − 2 ( n > 2 ). Тем самым получаем алгоритмпостроения Vn : к числам из Vn −1 нужно приписать «1», к числам из Vn − 2 — «2» и объединитьполученные множества.Обозначим через vn количество элементов в Vn , тогда v1 = 1 , v2 = 2 , vn = vn −1 + vn − 2 . Замечаем,что vn совпадает с (n + 1) -м числом Фибоначчи, т.е.

vn = vn −1 + vn − 2 = Fn +1 .Попробуем определить y (n) — число операций над числами (приписывание «1» или «2»).Для y (n) мы можем написать следующее рекуррентное соотношение:y (n) = y (n − 1) + y (n − 2) + Fn + Fn −1 ⇒14243Fn +1y (n) − y (n − 1) − y (n − 2) = Fn +1 , причём y (1) = y (2) = 0Обозначим затраты на объединение двух множеств через z (n) и, аналогично, получим дляz (n) следующее рекуррентное соотношение:z (n) − z (n − 1) − z (n − 2) = 1 ,(*)z (1) = z (2) = 0 (предполагаем, что V1 и V2 нам даны).Непосредственно видно, что − 1 является частным решением соотношения (*).

Частныерешения можно угадывать, но можно воспользоваться специальным методом их нахождения,который очень сильно похож на метод нахождения частных решений линейныхдифференциальных уравнений с постоянными коэффициентами. Суть метода заключается вследующем: рассмотрим однородное рекуррентное соотношениеad y (n) + ad −1 y (n − 1) + ... + a0 y (n − d ) = 0Составим по нему характеристическое уравнение, которое имеет вид:ad λd + ad −1λd −1 + ... + a0 = 0 ,которое, в свою очередь, будет иметь корни λ1 , λ2 , ... , λk (включая комплексные) сkкратностями m1 , m2 , ...