Простим називається ціле число, більше одиниці, єдиними множителями якого є 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
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 x = (((a + p - (b mod p)) * u) mod p) * q + b