>, а , то відповідь " < span align = "justify"> - складене ".
В іншому випадку відповідь " - просте".
Аналіз алгоритму.
Теорема 3.2. Якщо - просте, то описаний вище алгоритм завжди (з ймовірністю 1) видає відповідь " - просте".
Якщо - складене, то відповідь " - складене" буде отриманий з імовірністю .
Зауваження 3.2. Щоб отримати поліноміальний імовірнісний алгоритм перевірки простоти числа в сенсі визначення 3.1, потрібно двічі застосувати наведений алгоритм. Тоді ймовірність помилки стане менше .
Доказ (теореми 3.2). Зі сказаного вище випливає, що в доказі потребує тільки друге твердження. p align="justify"> Нехай , де (якщо такого подання немає, то на кроці 2 буде виявлена ​​непростота). Якщо , то перевірка 1 для такого завідомо виявить, що - складене. Так що досить довести, що не менше половини тих , які взаємно прості з , виявляють непростоту числа.
Позначимо групу через , групу - через . З китайської теореми про залишки випливає, що група ізоморфна (ізоморфізм задається природним чином - обчисленням залишків за модулем і по модулю ).
Розглянемо безлічі , . Це підгрупи в і відповідно (твір -х ступенів є -й ступінь, зворотний до -го ступеня є -й ступінь). Так що - ціле число. Більше того, відображення є гомоморфізмом груп, тому число прообразів при цьому відображенні однаково для всіх елементів . Очевидно, що (ступенів квадратів не більш, ніж усіх ступенів). Тому отримуємо пару незростаюча ланцюжків множин
В
Подальше міркування розбивається на аналіз декількох випадків.
Нехай або .
Щоб пройти перевірку 1 в алгоритмі, ...
