9. Арифметика сравнений

Описание 9-11 частей можно послушать в виде подкаста.

Начиная с этой части, при оценке сложности алгоритмов будем использовать обозначение $M(n)$, имея в виду сложность умножения двух чисел длины $n$. Можно показать (с помощью метода Ньютона), что деление нацело имеет ту же сложность, что и умножение, поэтому для деления отдельного обозначения вводить не будем.

Сложение и умножение по модулю

Сложение и умножение по $n$-битному модулю $N$ имеет ту же сложность, что и обычные сложение и умножение, то есть $O(n)$ и $O(M(n))$ : нужно произвести вычисление без модуля, при этом результат будем иметь не более $2 n$ бит, после чего вычислить остаток от деления результата на $N$. В случае сложения результат меньше $2 N$, поэтому достаточно просто (возможно) вычесть $N$, что требует ещё $O(n)$ операций и не увеличивает оценку времени работы. В случае умножения осуществляем деление с остатком за $O(M(n))$.

Возведение в степень по модулю $N$

Воспользуемся той же идеей, что и в рекурсивном алгоритме умножения:

1
2
3
4
5
6
7
8
9

def modExp(a, b, N):
    # a, b, N - целые числа
    if b == 0:
        return 1
    c = modExp(a, b // 2, N)  # целочисленное деление
    if b % 2 == 0:
        return (c * c) % N
    else:
        return (a * c * c) % N

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int modExp(int a, int b, int N) {
    if (b == 0) {
        return 1;
    }
    int c = modExp(a, b / 2, N);  // целочисленное деление
    if (b % 2 == 0) {
        return (c * c) % N;
    } else {
        return (a * c * c) % N;
    }
}

Если $n$ - максимальная длина чисел $a, b, N$, то происходит $O(n)$ рекурсивных вызовов, на каждом из которых не более двух умножений по модулю $N$. Получаем оценку сложности $O(n \cdot M(n))$.

Алгоритм Евклида

Алгоритм Евклида находит наибольший общий делитель (НОД, greatest common divisor, $\operatorname{gcd}$) двух чисел $a$ и $b$.

Алгоритм Евклида пользуется вышеописанным правилом, пока не окажется, что $b=0$. Ясно, что $\operatorname{gcd}(a, 0)=a$ для любого $a$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def gcd(a, b):  # a, b >= 0
    if b == 0:
        return a
    return gcd(b, a % b)


def gcd_iterative(a, b):  # нерекурсивная версия
    while b > 0:
        a %= b
        a, b = b, a  # swap(a, b)
    return a

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <utility>

// Рекурсивная версия
int gcd(int a, int b) {  // a, b >= 0
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Нерекурсивная версия
int gcd_iterative(int a, int b) {  // a, b >= 0
    while (b > 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

Оценим время работы алгоритма:

Если использовать алгоритм деления в столбик, можно показать оценку получше:

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

Расширенный алгоритм Евклида одновременно с $d=\operatorname{gcd}(a, b)$ находит такие $x$ и $y$, что $a x+b y=d$. Эти $x$ и $y$ можно использовать как сертификат, подтверждающий, что $d$ действительно НОД $a$ и $b$ :

Такие $x$ и $y$ всегда можно найти следующим алгоритмом:

1
2
3
4
5

def extendedEuclid(a, b):  # возвращает x,y такие, что ax + by = gcd(a, b)
    if b == 0:
        return 1, 0
    x, y = extendedEuclid(b, a % b)
    return y, x - (a // b) * y  # целочисленное деление

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <utility>

// возвращает x,y такие, что ax + by = gcd(a, b)
std::pair<int, int> extendedEuclid(int a, int b) {
    if (b == 0) {
        return {1, 0};
    }
    auto [x, y] = extendedEuclid(b, a % b);
    return {y, x - (a / b) * y}; 
}

Ясно, что число итераций этого алгоритма совпадает с числом итераций обычного алгоритма Евклида (так как рекурсивные переходы устроены точно так же). Чтобы оценить время работы расширенного алгоритма Евклида, нужно ещё понять, насколько большими могут быть $x$ и $y$ :

Пусть длина битовой записи $a$ и $b$ не превосходит $n$. Поскольку $a$ и $b$ только уменьшаются при рекурсивных вызовах, ясно, что все числа, возникающие в процессе промежуточных вычислений, имеют длину не более $n$. Теперь уже ясно, что оценка времени работы алгоритма Евклида $O(n \cdot M(n))$ остаётся верной и для расширенной версии.

Покажем, что остаётся верной и оценка $O\left(n^{2}\right)$ :

Нахождение обратного по модулю $N$

Число, обратное к $а$ по модулю $N\left(\right.$ об. $\left.a^{-1}\right)$ - это такое $x$, что $a x \equiv 1(\bmod N)$. Такое $x$ существует тогда и только тогда, когда $a x+N y=1$ для некоторого $y$. Как мы уже знаем, такое уравнение имеет решение только когда $\operatorname{gcd}(a, N)=1$, то есть когда $a$ взаимно просто с $N$.

С помощью расширенного алгоритма Евклида мы можем за $O\left(n^{2}\right)$ проверить, существует ли обратное к $a$ по модулю $N$, и если существует, то найти его.

Если для числа $a$ существует обратное по модулю $N$ число $a^{-1}$, то можно осуществлять деление на $a$ по модулю $N$ : это равносильно умножению на $a^{-1}$.