Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два -- это простое число. Простыми являются и 73, 2521, 2365347734339 и 2756839-1. Существует бесконечно много простых чисел. Криптография, особенно криптография с открытыми ключами, часто использует большие простые числа (512 бит и даже больше).

Два числа называются взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, если наибольший общий делитель a и n равен 1. Это записывается как:
НОД (a,n)=1

Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 -- являются. Простое число взаимно просто со всеми другими числами, кроме чисел, кратных данному простому числу.
Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвклид описал этот алгоритм в своей книге «Элементы» написанной в 300 году до нашей эры. Он не изобрел его. Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации.

Помните, что такое обратные значения? Обратное значение для 4 -- 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:
4*x = 1 (mod 7)
Это уравнение эквивалентно обнаружению x и k, таких что
4x = 7k + 1
где x и k - целые числа. Общая задача состоит в нахождении x, такого что
1 = (a*x) mod n
Это также можно записать как
a-1 = x (mod n)
Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.
В общем случае для уравнения a-1= x (mod n) существует единственное решение, если a и n взаимно просты. Если a и n не являются взаимно простыми, то a-1 = x (mod n) не имеет решений. Если n является простым числом, то любое число от 1 до n-1 взаимно просто с n и имеет в точности одно обратное значение по модулю n.
Так, хорошо. А теперь как вы собираетесь искать обратное значение a по модулю n? Существует два пути. Обратное значение a по модулю n можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.
Алгоритм итеративен и для больших чисел может работать медленно. Кнут показал, что среднее число выполняемых алгоритмом делений равно:
0.843*log2(n) + 1.47.
Решение для коэффициентов
Алгоритм Эвклида можно использовать и для решения следующих проблем: дан массив из m переменных x1, x2, ..., xm, найти массив m коэффициентов, ul, u2, ..., um, таких что
ul * x1+...+ um * xm, = 1
Китайская теорема об остатках
Если известно разложение числа n на простые сомножители, то для решения полной системы уравнений можно воспользоваться Китайской теоремой об остатках. Основной вариант этой теоремы был открыт в первом веке китайским математиком Сун Цзе.
В общем случае, если разложение числа n на простые сомножители представляет собой p1*p2*...*pt, то система уравнений
(x mod pi) = ai, где i = 1, 2, . . . , t
имеет единственное решение, x, меньшее n. (Обратите внимание, что некоторые простые числа могут появляться несколько раз. Например, p1 может быть равно p2.) Другими словами, число (меньшее, чем произведение нескольких простых чисел) однозначно определяется своими остатками от деления на эти простые числа.
Например, возьмем простые числа 3 и 5, и 14 в качестве заданного числа. 14 mod 3 = 2, и 14 mod 5 = 4. Существует единственное число, меньшее 3*5 = 15, с такими остатками: 14. Два остатка однозначно определяют число.
Поэтому для произвольного a < p и b < q (где p и q -- простые числа), существует единственное число x, меньшее pq, такое что
x = a (mod p), и x = b (mod q)
Для получения x сначала воспользуемся алгоритмом Эвклида, чтобы найти u, такое что
u*q 1 (mod p)
Затем вычислим:
x = (((a - b) *u) mod p) * q + b
Обращение Китайской теоремы об остатках может быть использовано для решения следующей проблемы: если p и q - простые числа, и p меньше q, то существует единственное x, меньшее, чем pq, такое что
a = x (mod p), и b = x (mod q)
Если a >=b mod p, то
x = (((a - (b mod p)) * u) mod p) * q + b
Если a < b mod p, то
x = (((a + p - (b mod p))*u) mod p)*q + b