алгоритм Евкліда
Свій відомий алгоритм Евклід придумав для вирішення завдання про сумірності двох відрізків. Загальною мірою відрізків з довжинами L 1 і L 2 називається відрізок з найбільшою можливою довжиною L. який можна укласти без залишку як в першому відрізку, так і в другому. Як відомо, алгоритм полягає в наступному. Менший відрізок (довжини L 2) укладається в більшій (довжини L 1) максимально можливе число, скажімо a 1. раз, після чого залишається відрізок довжини L 1 - a 1 L 2. який позначимо L 3. Потім повторюємо цю операцію з L 2 і L 3 і т. д. Роботу алгоритм закінчує на тому етапі, скажімо з номером k. коли отриманий на попередньому кроці відрізок L k +1 укладається на відрізку L k ціле число раз. Відповіддю буде L k +1.
Розширений алгоритм Евкліда
Трохи доповнивши алгоритм Евкліда, можна отримувати з його допомогою цілі коефіцієнти x і y. для яких
(A. B) = GCD (a. B) = a x + b y
GCD - Greatest Common Divisor (Найбільший Загальний Дільник)
Час роботи алгоритму Евкліда
Позначимо e (m. N) число кроків алгоритму Евкліда, застосованого до натуральних числах n і m. До цих пір найбільш відомим результатом про функції e (m. N) залишається знайдена французьким математиком Габріелем Ламі (Gabriel Lamé, 1795-1870) в першій половині 19-го століття (1844) оцінка зверху:
e (m. n) ≤ [logφ 5 1/2 (max (m. n) + 1/2)] - 1, де φ = (1 + 5 1/2) / 2
Дана оцінка є точною і досягається при сусідніх числах Фібоначчі: m = F k +1. n = F k.
Доказ і різні інтерпретації алгоритму Евкліда см. [5]
Порівняння по модулю
Два цілих числа a і b називаються порівнянними за модулем m. якщо a - b ділиться на m.
a ≡ b (mod m) ↔ m | (A - b)
Кожне натуральне число можна порівняти з одним із чисел по модулю m.
Кільце відрахувань Z / n Z
Всі залишки по модулю n утворюють кільце відрахувань, що позначається Z / n Z. Число елементів в кільці Z / n Z одно n. Наприклад, кільце Z / 6 Z складається з 6 елементів:.
Дії в кільці Z / n Z
Елементи цього кільця можна складати, віднімати і множити як звичайні числа. Наприклад, в кільці Z / 6 Z виконуються наступні рівності:
2 + 3 ≡ 5 (mod 6)
3 - 5 ≡ 4 (mod 6)
2 · 4 ≡ 2 (mod 6)
Розподіл в Z / n Z
Розподіл в кільці Z / n Z можливо не завжди. Наприклад, в кільці Z / 8 Z можна розділити 1 на 2, зате можна розділити 2 на 3 (вийде 6). З чим же пов'язана неможливість поділу в деяких випадках? Щоб розібратися в цьому, визначимо, що ж таке розподіл.
Нехай нам задано рівняння
a x ≡ b (mod m)
У ньому a і b - параметри, x - невідоме.
Якщо такий x існує і єдиний, то x називається часткою від ділення b на a.
Перепишемо це рівняння таким чином:
Очевидно, що якщо b не ділиться на (a. M), то рішень немає і розподіл неможливо. (Ось чому 1 можна розділити на 2 в Z / 8 Z) Для вирішення даного рівняння знайдемо x. y. такі що
Так як b = w (a. M), то отримуємо:
b = a (x w) + m (y w)
Отже, ми знайшли одне з рішень рівняння a x ≡ b (mod m) Нескладно показати, що у цього рівняння буде рівно (a. M) рішень.
Таким чином, розподіл b на a в Z / n Z можливо тільки в разі, коли (a. M) = 1. Якщо n - просте, то розподіл в Z / n Z можливо на всі елементи, відмінні від нуля.
модулярная арифметика
Модулярная арифметика грунтується на так званій Китайській теоремі про залишки (КТО). Близько 100 р. До н.е. е. китайський математик Сун Цу (Sun-Tsu) вирішив таке завдання: знайти число, що дає при діленні на 3, 5, 7, залишки 2, 3, 2 відповідно.
Китайська теорема про залишки
Нехай n = n 1 n 2 ... n k. Причому числа n 1. n 2. ..., n k попарно взаємно прості. Розглянемо відповідність
де a i - залишок від ділення a на n i. Тоді воно задає взаємно однозначна відповідність між Z / n Z і Z / n 1 Z × ... × Z / n k Z.
функція Ейлера
Функція Ейлера φ (a) визначається для всіх натуральних a і являє собою кількість чисел від 1 до a взаємно простих з a. приклади:
Чому дорівнює φ (239)?
Нескладно показати, що функція Ейлера мультипликативна, тобто, для будь-яких n і m таких, що (n. M) = 1 виконується
φ (n m) = φ (n) φ (m)
Очевидно, що для простого p виконуються рівності:
φ (p) = p - 1,
φ (p n) = p n -1 (p - 1)
Ці властивості дозволяють швидко обчислювати функцію Ейлера, якщо відомо розкладання числа n на прості множники.
Цікаво, а існують такі n. що φ (n) = 239?
Теореми Ейлера і Ферма
Теорема (Ейлер)
При m> 1 і (a. M) = 1 вірно наступне:
a φ (m) ≡ 1 (mod m)
Теорема (Ферма)
Для будь-якого простого p і будь-якого натурального a вірно наступне:
a p ≡ a (mod p)
Дихотомічне спорудження до рівня
Піднесення до степеня за модулем грає важливу роль при перевірці чисел на простоту, а також в криптосистеме RSA.
первісні корені
Нехай p - просте число. Тоді, як відомо, Z / p Z є полем. Порядком відрахування a> 0 називається найменше натуральне число m таке, що
a m ≡ 1 (mod p)
Відповідно до малої теореми Ферма, хоча б одне таке m існує (і так само p -1).
Для будь-якого простого p існує відрахування g порядку p -1.
Ці вирахування g називається первісним коренем за модулем p.
Нескладно також показати, що таких відрахувань існує рівно φ (p -1).
З розширеної гіпотези Рімана (див. [3], стр. 112) слід, що найменший первісний корінь по модулю p обмежений величиною O (log 6 p).
Перевірка чисел на простоту
Найпростіший спосіб перевірити, скільки n на простоту - перебір дільників (trial division).
Тест на основі малої теореми Ферма
Мала теорема Ферма стверджує, що якщо n просте, то виконується умова: при всіх a з має місце порівняння
a n -1 ≡ 1 (mod n) (1)
З цієї теореми випливає, що якщо порівняння (1) не виконано хоча б для одного числа a в інтервалі, то n - складене. Тому можна запропонувати наступний імовірнісний тест простоти:
- вибираємо випадкове число a з і перевіряємо за допомогою алгоритму Евкліда умову (a. n) = 1;
- якщо воно не виконується, то відповідь «n - складене»;
- перевіряємо здійсненність порівняння (1);
- якщо порівняння не виконано, то відповідь «n - складене»;
- якщо порівняння виконано, то відповідь невідомий, але можна повторити тест ще раз.
a n -1 ≡ 1 (mod n)
Імовірнісний тест Міллера-Рабіна
Нехай n - непарне і n - 1 = 2 s t. t - непарне.
Якщо число n є простим, то при всіх a> 1 виконується порівняння
a n -1 ≡ 1 (mod n)
Тому, розглядаючи елементи можна помітити, що або серед них знайдеться рівний -1 (mod n), або a t ≡ 1 (mod n).
На цьому зауваженні заснований наступний імовірнісний тест простоти:
- вибираємо випадкове число a з інтервалу і перевіряємо за допомогою алгоритму Евкліда умову (a. n) = 1;
- якщо воно не виконується, то відповідь «n - складене»;
- обчислюємо a t (mod n);
- якщо a t ≡ ± 1 (mod n), то переходимо до п. 1;
- обчислюємо a 2 t. ..., a 2 s -1 t до тих пір, поки не з'явиться -1;
- якщо жодна з цих чисел не дорівнює -1, то відповідь «n - складене»;
- якщо ми досягли -1, то відповідь невідомий (і тест можна повторити ще раз).
Складене число не буде визначено як складене з ймовірністю 1 / 4. (див. [1]).
Якщо вірна розширена гіпотеза Рімана, то досить перевіряти всі a з (див. [3]).
Додаток. Деякі поняття з алгебри
Визначення. Полем називається безліч K з двома заданими на ньому бінарними операціями · і +, які задовольняють таким умовам:
- (A + b) + c = a + (b + c) і (a · b) · c = a · (b · c) для всіх a. b. c ∈ K (асоціативність)
- a + b = b + a і a · b = b · a для всіх a. b ∈ K (коммутативность)
- a · (b + c) = a · b + a · c для всіх a. b. c ∈ K (дистрибутивность)
- Існують елементи 0 і 1, звані нулем і одиницею відповідно, такі, що a + 0 = a · 1 = a для будь-якого a ∈ K
- Для будь-якого елементу a ∈ K існує елемент b. такий, що a + b = 0 (існування адитивної зворотного)
- Для будь-якого елементу a ∈ K. не дорівнює нулю, існує елемент c. такий, що a · c = 1 (існування мультиплікативного зворотного)
Визначення. Кільцем (або комутативним кільцем) називається безліч R з двома заданими на ньому бінарними операціями · і +, які задовольняють таким умовам:
- (A + b) + c = a + (b + c) і (a · b) · c = a · (b · c) для всіх a. b. c ∈ R (асоціативність)
- a + b = b + a і a · b = b · a для всіх a. b ∈ R (коммутативность)
- a · (b + c) = a · b + a · c для всіх a. b. c ∈ R (дистрибутивность)
- Існують елементи 0 і 1, звані нулем і одиницею відповідно, такі, що a + 0 = a · 1 = a для будь-якого a ∈ R
- Для будь-якого елементу a ∈ R існує елемент b. такий, що a + b = 0 (існування адитивної зворотного)
Визначення. Групою називається безліч G із заданою на ньому бінарної операцією ·, яка задовольняє таким умовам:
- (A · b) · c = a · (b · c) для всіх a. b. c ∈ G (асоціативність)
- Існує елемент 1, званий одиницею. такий, що a · 1 = 1 · a = a для будь-якого a ∈ G
- Для будь-якого елементу a ∈ G існує елемент b. такий, що a · b = b · a = 1 (існування зворотного елемента)
література
Михайло Лукін, Роман Сатюков
Спасибі, дуже допомогло. )