Первая страница / Теория / Компьютерная математика /

Теория чисел

Голосование: 20, 4

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

Свой известный алгоритм Евклид придумал для решения задачи о соизмеримости двух отрезков. Общей мерой отрезков с длинами L1 и L2 называется отрезок с наибольшей возможной длиной L, который можно уложить без остатка как в первом отрезке, так и во втором. Как известно, алгоритм заключается в следующем. Меньший отрезок (длины L2) укладывается в большем (длины L1) максимально возможное число, скажем a1, раз, после чего остается отрезок длины L1 − a1L2, который обозначим L3. Затем повторяем эту операцию с L2 и L3 и т. д. Работу алгоритм заканчивает на том шаге, скажем с номером k, когда полученный на предыдущем шаге отрезок Lk+1 укладывается на отрезке Lk целое число раз. Ответом будет Lk+1.

Euclid(a, b)
1   if (b = 0)
2       return a
3   else
4       return Euclid(b, a mod b)

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

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

(ab) = GCD(ab) = ax + by

GCD — Greatest Common Divisor (Наибольший Общий Делитель)

Extended-Euclid(a, b)
1   if (b = 0)
2       return (a, 1, 0)
3   (dd, xx, yy) ← Extended-Euclid(b, a mod b)
4   (d, x, y) ← (dd, yy, xx − [a/b]yy)
5   return (d, x, y)

Время работы алгоритма Евклида

Обозначим e(mn) число шагов алгоритма Евклида, примененного к натуральным числам n и m. До сих пор наиболее известным результатом о функции e(mn) остается найденная французским математиком Габриэлем Ламе (Gabriel Lamé, 1795–1870) в первой половине 19-го века (1844) оценка сверху:

e(mn) ≤ [logφ51⁄2(max(mn) + 1⁄2)] − 1, где φ = (1 + 51⁄2) ⁄ 2

Данная оценка является точной и достигается при соседних числах Фибоначчи: m = Fk+1, n = Fk.

Доказательство и различные интерпретации алгоритма Евклида см. [5]

Сравнения по модулю

Два целых числа a и b называются сравнимыми по модулю m, если a − b делится на m.

a ≡ b (mod m) ⇔ m | (a − b)

Каждое натуральное число сравнимо с одним из чисел {0, 1, …, m−1} по модулю m.

Кольцо вычетов Z/nZ

Все остатки по модулю n образуют кольцо вычетов, обозначаемое Z/nZ. Число элементов в кольце Z/nZ равно n. Например, кольцо Z/6Z состоит из 6 элементов: {0, 1, 2, 3, 4, 5}.

Действия в кольце Z/nZ

Элементы этого кольца можно складывать, вычитать и умножать как обычные числа. Например, в кольце Z/6Z выполняются следующие равенства:

2 + 3 ≡ 5 (mod 6)
3 − 5 ≡ 4 (mod 6)
2 · 4 ≡ 2 (mod 6)

Деление в Z/nZ

Деление в кольце Z/nZ возможно не всегда. Например, в кольце Z/8Z нельзя разделить 1 на 2, зато можно разделить 2 на 3 (получится 6). С чем же связана невозможность деления в некоторых случаях? Чтобы разобраться в этом, определим, что же такое деление.

Пусть нам задано уравнение

ax ≡ b (mod m)

В нем a и b — параметры, x — неизвестное.
Если такой x существует и единственный, то x называется частным от деления b на a.

Перепишем это уравнение следующим образом:

ax + cm = b

Очевидно, что если b не делится на (am), то решений нет и деление невозможно. (Вот почему 1 нельзя разделить на 2 в Z/8Z) Для решения данного уравнения найдем x, y, такие что

(am) = ax + my

Так как b = w(am), то получаем:

b = a(xw) + m(yw)

Итак, мы нашли одно из решений уравнения ax ≡ b (mod m) Несложно показать, что у этого уравнения будет ровно (am) решений.

Таким образом, деление b на a в Z/nZ возможно только в случае, когда (am) = 1. Если n — простое, то деление в Z/nZ возможно на все элементы, отличные от нуля.

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

Модулярная арифметика основывается на так называемой Китайской теореме об остатках (КТО). Около 100 г. до н. э. китайский математик Сун Цу (Sun-Tsu) решил такую задачу: найти число, дающее при делении на 3, 5, 7, остатки 2, 3, 2 соответственно.

Китайская теорема об остатках

Пусть n = n1n2nk. Причем числа n1, n2, …, nk попарно взаимно просты. Рассмотрим соответствие

a ↔ (a1, a2, …, ak)

где ai — остаток от деления a на ni. Тогда оно задает взаимно однозначное соответствие между Z/nZ и Z/n1Z × … × Z/nkZ.

Подробнее о модулярной арифметике см. [2], стр. 325–333.

Функция Эйлера

Функция Эйлера φ(a) определяется для всех натуральных a и представляет собою количество чисел от 1 до a взаимно простых с a. Примеры:

φ(1) = 1, φ(4) = 2,
φ(2) = 1, φ(5) = 4,
φ(3) = 2, φ(6) = 2.

Чему равно φ(239)?

Несложно показать, что функция Эйлера мультипликативна, то есть, для любых n и m таких, что (nm) = 1 выполняется

φ(nm) = φ(n)φ(m)

Очевидно, что для простого p выполняются равенства:

φ(p) = p − 1,
φ(pn) = pn−1(p − 1)

Эти свойства позволяют быстро вычислять функцию Эйлера, если известно разложение числа n на простые множители.

Интересно, а существуют такие n, что φ(n) = 239?

Теоремы Эйлера и Ферма

Теорема (Эйлер)

При m > 1 и (am) = 1 верно следующее:

aφ(m) ≡ 1 (mod m)

Теорема (Ферма)

Для любого простого p и любого натурального a верно следующее:

ap ≡ a (mod p)

Подробнее о теоремах Ферма и Эйлера см. [6].

Дихотомическое возведение в степень

Возведение в степень по модулю играет важную роль при проверке чисел на простоту, а также в криптосистеме RSA.

Power(a, n, m)
1   p ← 1
2   q ← a
3   while n > 0
4       if n ≡ 1 (mod 2) then
5           p = p·q mod m
6       q ← q·q mod m
7       n ← n/2
8   endwhile
9   return p

Первообразные корни

Пусть p — простое число. Тогда, как известно, Z/pZ является полем. Порядком вычета a > 0 называется наименьшее натуральное число m такое, что

am ≡ 1 (mod p)

Согласно малой теореме Ферма, хотя бы одно такое m существует (и равно p−1).

Теорема

Для любого простого p существует вычет g порядка p−1.

Такой вычет g называется первообразным корнем по модулю p.

Несложно также показать, что таких вычетов существует ровно φ(p−1).

Из расширенной гипотезы Римана (см. [3], стр. 112) следует, что наименьший первообразный корень по модулю p ограничен величиной O(log6p).

Подробнее о первообразных корнях см. [6] и [3].

Проверка чисел на простоту

Самый простой способ проверки числа n на простоту — перебор делителей (trial division).

Prime(n)
1   for i ← 2 to [n1/2] do
2       if (n ≡ 0 mod i) then
3           return COMPOSITE
4   return PRIME

Тест на основе малой теоремы Ферма

Малая теорема Ферма утверждает, что если n простое, то выполняется условие: при всех a из {1, 2, …, n−1} имеет место сравнение

an−1 ≡ 1 (mod n)   (1)

Из этой теоремы следует, что если сравнение (1) не выполнено хотя бы для одного числа a в интервале {1, 2, …, n−1}, то n — составное. Поэтому можно предложить следующий вероятностный тест простоты:

  1. выбираем случайное число a из {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (an) = 1;
  2. если оно не выполняется, то ответ «n — составное»;
  3. проверяем выполнимость сравнения (1);
  4. если сравнение не выполнено, то ответ «n — составное»;
  5. если сравнение выполнено, то ответ неизвестен, но можно повторить тест еще раз.

Числа Кармайкла (Carmichael Numbers)

Особо плохими для теста Ферма являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что (an) = 1 верно

an−1 ≡ 1 (mod n)

Первые три числа Кармайкла таковы: 561, 1105, 1729. Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много.

Вероятностный тест Миллера-Рабина

Пусть n — нечетное и n − 1 = 2st, t — нечетное.

Если число n является простым, то при всех a > 1 выполняется сравнение

an−1 ≡ 1 (mod n)

Поэтому, рассматривая элементы {at, a2t, …, a2s−1t} можно заметить, что либо среди них найдется равный −1 (mod n), либо at ≡ 1 (mod n).

На этом замечании основан следующий вероятностный тест простоты:

  1. выбираем случайное число a из интервала {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (an) = 1;
  2. если оно не выполняется, то ответ «n — составное»;
  3. вычисляем at (mod n);
  4. если at ≡ ±1 (mod n), то переходим к п. 1;
  5. вычисляем a2t, …, a2s−1t до тех пор, пока не появится −1;
  6. если ни одно из этих чисел не равно −1, то ответ «n — составное»;
  7. если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз).

Составное число не будет определено как составное с вероятностью 1 ⁄ 4. (см. [1]).

Теорема

Если верна расширенная гипотеза Римана, то достаточно проверять все a из {2, 3, …, [2log2n]+1} (см. [3]).

Приложение. Некоторые понятия из алгебры

Определение. Полем называется множество K с двумя заданными на нем бинарными операциями · и +, которые удовлетворяют следующим условиям:

  1. (a + b) + c = a + (b + c) и (a · b) · c = a · (b · c) для всех a, b, c ∈ K (ассоциативность)
  2. a + b = b + a и a · b = b · a для всех a, b ∈ K (коммутативность)
  3. a · (b + c) = a · b + a · c для всех a, b, c ∈ K (дистрибутивность)
  4. Существуют элементы 0 и 1, называемые нулем и единицей соответственно, такие, что a + 0 = a · 1 = a для любого a ∈ K
  5. Для любого элемента a ∈ K существует элемент b, такой, что a + b = 0 (существование аддитивного обратного)
  6. Для любого элемента a ∈ K, не равного нулю, существует элемент c, такой, что a · c = 1 (существование мультипликативного обратного)

Определение. Кольцом (или коммутативным кольцом) называется множество R с двумя заданными на нем бинарными операциями · и +, которые удовлетворяют следующим условиям:

  1. (a + b) + c = a + (b + c) и (a · b) · c = a · (b · c) для всех a, b, c ∈ R (ассоциативность)
  2. a + b = b + a и a · b = b · a для всех a, b ∈ R (коммутативность)
  3. a · (b + c) = a · b + a · c для всех a, b, c ∈ R (дистрибутивность)
  4. Существуют элементы 0 и 1, называемые нулем и единицей соответственно, такие, что a + 0 = a · 1 = a для любого a ∈ R
  5. Для любого элемента a ∈ R существует элемент b, такой, что a + b = 0 (существование аддитивного обратного)

Определение. Группой называется множество G с заданной на нем бинарной операцией ·, которая удовлетворяет следующим условиям:

  1. (a · b) · c = a · (b · c) для всех a, b, c ∈ G (ассоциативность)
  2. Существует элемент 1, называемый единицей, такой, что a · 1 = 1 · a = a для любого a ∈ G
  3. Для любого элемента a ∈ G существует элемент b, такой, что a · b = b · a = 1 (существование обратного элемента)

Литература

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
  2. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд. — М.: Издательский дом «Вильямс», 2001.
  3. Введение в криптографию, 2-е изд., испр. / Под общ. ред. В.В.Ященко. — М.: МЦНМО-«ЧеРо», 1999.
  4. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии — М.: МЦНМО, 2003.
  5. Журнал «Математическое просвещение», вып. 4-7. — М.: МЦНМО, 2000-2003.
  6. Виноградов И.М. Элементы высшей математики. — M.: Высшая школа, 1999.

Михаил Лукин, Роман Сатюков


Максим / 2011-01-12 13:53:59

Спасибо, очень помогло! :)

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий