19. Перевірка чисел на взаємну простоту (розширений алгоритм Евкліда). Теореми Міллера-Рабіна та Ферма.

Відзначимо, що значення a_i може бути обчислено як MOD(a_i-2, a_i-1), але гідність наведеного вище виразу полягає в тому, що a_i обчисляється аналогічно вирахуванню коефіцієнтів x_i і y_i. Цей факт використовується в наступному алгоритмі.

Нехай n - велике непарне число, і ми хочемо визначити чи є n простим.

Теорема (Ферма). Якщо n - просте число, то згідно малої теореми Ферма для будь-якого такого b, що НОД (b, n) =1, . (1)

Якщо n - не просте число, то (1) теж може виконуватись (хоча це малоймовірно).

Визначення. Якщо n - непарне складене число, b - ціле число, НОД (n, b) =1, і (1) виконується, то n називається псевдопростим числом за основою b.

Іншими словами, "псевдопросте" число - це число n, яке "претендує" бути простим, проходячи тест (1).

Приклад 1. число n = 91 - псевдопросте за основою b = 3, так як . Однак, 91 не є псевдопростим числом за основою 2, так як . Якщо б ми ще не знали, що 91 складене число, то с піввідношення довело б нам це.

Сильно псевдопросте число. Розглянем тепер ще один вид критеріїв простоти, що у певному сенсі навіть краще тесту Соловея - Штрассе, заснованого на взначенні псевдо простати по Ейлеру. Це тест Міллера-Рабіна, заснований на понятті "сильно псевдо простати". Припустим, що n – велике непарне натуральне число і . Нехай, далі, n - псевдопросте за основою b, тобто . Ідея критерію сильної псевдо простати така. Нехай , t - непарне. Якщо послідовно обчислювати , то при простому n першим елементом, відмінним від 1, повинен бути елемент 1, так як при простому n єдиним рішенням порівняння  є +1 і-1. практично дії виконуються "у зворотному порядку". Вважаємо , t - непарне. Обчислюємо  по модулю n. Якщо , зводимо в квадрат по модулю n, отримуємо , потім знову зводимо в квадрат і т.д. до тих пір, поки не отримаємо 1: . Тоді, якщо n - просте, попереднім числом має бути - 1, в іншому випадку ми отримуємо доказ того, що n складене.

Визначення. Нехай n - непарне складене число і n-1=2^st, t -непарне. Нехай . Якщо n і b задовольняють одну з умов:

1) ;

2) існує таке r, , що

 (2)

то n називають сильно псевдопростим за основою b.

Тест Міллера-Рабіна. Припустимо, що ми хочемо визначити, є велике натуральне число n простим чи складним. Уявімо n-1 у вигляді , t непарне, і виберемо випадкове ціле число b, 0<b<n. Спочатку обчислюємо  по модулю n. Якщо виходить , то висновком, що n пройшло тест (2) при даному b, і робимо новий випадковий вибір b. В іншому випадку зводимо  в квадрат по модулю n, результат знову зводимо в квадрат по модулю n і продовжуємо так до тих пір, поки не отримаємо - 1. Якщо це відбуватиметься, то ми вважаємо, що n пройшло тест. Якщо ж це не відбуважться, тобто якщо ми отримуємо , у той час як , то n не проходить тест, і це доводить, що n - складене число. Якщо ми k раз випадково вибирали різі основи b і n кожен раз проходило відповідний тест, то число n має не більше  шансу бути складеним.