Доказательство

[показать]

▪ НОД(0,‪r) = ‪r для любого ненулевого ‪r (т.к. 0 делится на любое целое число, кроме нуля).

Проще сформулировать алгоритм Евклида так: если даны натуральные числа ‪a и ‪b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

[править]

Пример

Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим знаменатель меньше чем 462. Мы должны дважды отнять 462, (q₀ = 2), оставаясь с остатком 147

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q₁ = 3), оставаясь с остатком 21.

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q₂ = 7), оставаясь без остатка.

147 = 7 × 21 + 0.

Таким образом последовательность a>b>R₁>R₂>R₃>R₄>...>R_n в данном конкретном случае будет выглядеть так:

1071>462>147>21


Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21.

В табличной форме, шаги были следующие

Свидетели простоты и теорема Рабина

Пусть — нечётное число большее 1. Число однозначно представляется в виде , где нечётно. Целое число , , называется свидетелем простоты числа , если выполняется одно из условий:

▪

или

▪ существует целое число , , такое, что

Теорема Рабина утверждает, что составное нечётное число ‪m имеет не более ‪φ(m) / 4 различных свидетелей простоты, где ‪φ(m) — функция Эйлера.

[править]

Алгоритм Миллера — Рабина

Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины ‪log ₂(m), где m — проверяемое число.

Для данного m находятся такие целое число s и целое нечётное число t, что ‪m − 1 = 2^st. Выбирается случайное число a, 1 < a < m. Если a не является свидетелем простоты числа m, то выдается ответ «m составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдается ответ «m, вероятно, простое», и алгоритм завершается.

Алгоритм может быть записан на псевдокоде следующим образом:

Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту;

r — количество раундов.

Вывод: составное, означает, что m является составным числом;

вероятно простое, означает, что m с высокой вероятностью является простым числом.

Представить m − 1 в виде 2^s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.

цикл А: повторить r раз:

Выбрать случайное целое число a в отрезке [2, m − 2]

x ← a^t mod m

если x = 1 или x = m − 1, то перейти на следующую итерацию цикла А

цикл B: повторить s − 1 раз

x ← x² mod m

если x = 1, товернуть составное

если x = m − 1, то перейти на следующую итерацию цикла А

вернуть составное

вернуть вероятно простое

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа m, то вероятность того, что m составное, не превосходит ‪4^-r.