Схема алгоритму на базі малої теореми Ферма.
Дане число n і параметр g = 1 для ідентифікації результату перевірки.
1) робиться випадковий вибір цілого числа a і інтервалу [2, n];
2) використовуючи алгоритм Евкліда, обчислюється НСД для чисел a і n;
3) якщо НСД більше 1, то виконується крок 7;
4) для числа a перевіряється рівняння a
n
- 1
≡ 1 mod n;
5) якщо рівняння не виконується, то визначається параметр g = 0 (число складене) перехід на крок 7.
6) якщо рівняння виконується, то можна повторити тест;
7) видати результат перевірки (g = 0 – число складене). Для будь-якого простого числа n і будь-якого a > 2 такого, що (a
2
- 1, n
) = 1, число (a
2n
- 1)/(a
2
-
1)
є псевдопростим по основі a.
Визначення. Складені числа n, для яких при всіх основах виконується рівняння a
n
- 1
≡ 1 mod n
, називаються числами Кармайкла.
Схема алгоритму на базі малої теореми Ферма.
Дано число n і параметр g = 1 для ідентифікації результату перевірки.
1) робиться випадковий вибір цілого числа a з інтервалу [2, n];
2) використовуючи алгоритм Евкліда, обчислюється НСД для чисел a і n;
3) якщо НСД більше 1, то виконується крок 7;
4) для числа a перевіряється рівняння a
n
- 1
≡ 1 mod n;
5) якщо рівняння не виконується, то визначається параметр g = 0 (число складене) перехід на крок 7.
6) якщо рівняння виконується, то можна повторити тест;
7) видати результат перевірки (g = 0 – число складене).
При завершенні роботи алгоритму можливі наступні висновки: число n – складене (g = 0); якщо g = 1, то число n є або простим, або складовим і числом
Кармайкла.
Тут доречно помітити, що числа Кармайкла досить рідкі. Так існують усього 2 163 чисел Кармайкла, які не перевершують 25 000 000 000, і всього 16 чисел, які не перевершують числа 100 000.
Тест Соловея – Штрассена.
Тест Соловея - Штрассена перевірки на простоту числа p базується на теоремі 4.
Теорема 4. Для будь-якого непарного n наступні умови еквівалентні:

· n – просте;
· для любого a ∈ Zn виконується рівняння a
(n - 1)/2
mod n
≡ L(a, n), де Z*n– мультипликативна група,елементами якої є a ∈ Zn (Zn –кільце віднімань по модулю n).
Для перевірки простоти числа p використовується алгоритм обчислення символу Якобі.
Схема алгоритму на базі малої теореми Ферма.
Нехай дано непарне число p. Треба перевірити чи є число p простим.
1. Вибирається випадкове число a, менше p.
2. Якщо НСД (a, p) ≠ 1, то p – складене число.
3. Обчислюється порівняння L(a, p) ≠ a
(p - 1)/2
mod p.
4. Обчислюється символ Якобі J(a, p).
5. Якщо L(a, p) ≠ J(a, p), то число p – складене.
6. Якщо L(a, p) = J(a, p), то ймовірність того, що число p – складене не перевищує 50 %.
Якщо перевірка повторюється k раз, то ймовірність того, що число p – складене, не перевищує 1/2k.
Тест Рабіна – Міллера.
Обґрунтування алгоритму Рабіна - Міллера можна знайти в літературі.
Тут дамо тільки самі загальні розуміння. Відомо, що якщо число p – просте, то рівняння x
2
≡ 1 mod p
має лише два розв'язки: x ≡ ±1 mod p. Отже, нехай p – непарне ціле число, яке треба перевірити на простоту. Якщо p – просте, то по теоремі Ферма для будь-якого цілого a взаємно простого з p виконується рівняння a
m - 1
≡ 1 mod p
. Тому що p - 1 – парне, то одержуємо a
(m - 1)/2
≡ ±1 mod
p
. Якщо виявляється, що (m - 1)/2 – парне, то можна повторити міркування, при якому одержимо, що a(m - 1)/4 ≡ ±1 mod p, і т.д.
Тому, щоб перевірити на простоту непарне число p, вибираємо випадковим чином число a з інтервалу [1, p - 1] і обчислюємо
a
t
mod p, a
2t
mod p, …, abt mod p, де t – непарне й число b = 2
s
. Якщо одне із цих чисел не збігається з +1 або -1, то можна зробити висновок, що число p є числом складовим. Якщо значення чисел збігаються з +1 або -1, то повторюємо цей тест k раз. Після повторення цього тесту k раз імовірність того, що складене число p не буде виявлено, не перевершує 1/4
k
. Після висловлених міркувань перейдемо до формулювання алгоритму Рабіна - Міллера.
У деякій літературі даний алгоритм називають тестом Міллера - Рабіна.

Схема алгоритму Рабіна - Міллера
Нехай дано непарне число p. Треба перевірити чи є число p простим. Далі припустимо, що p - 1 = 2
St
1. Вибираємо випадкове число a, менше p і визначаємо k = 0.
2. Обчислюємо за допомогою алгоритму Евкліда НСД двох чисел a і p.
Якщо НСД (a, p) ≠ 1, то p – складене число.
3. Обчислюємо b ≡ a
t
mod p
. Якщо b = 1 або b = p - 1, то число p імовірно просте.
4. Якщо b ≠ 1 і b ≠ p - 1, то обчислюємо b ≡ b
2
mod p
і k= k + 1.
5. Якщо число b = p - 1, то число p імовірно просте. Перейти на крок 7.
6. Поки k < s виконувати пункт 4.
7. Завершити роботу алгоритму.
Розглянемо приклади.
Приклад. Нехай p = 181. Маємо p - 1 = 45 ・ 2 2
. По представленому розкладанню визначаємо значення параметра t = 45.
1. Вибираємо випадкове число a = 52 < p, і визначаємо k = 0.
2.
Використовуємо алгоритм Евкліда для обчислення НСД двох чисел 52 і
181: ділимо число 181 на число 52, одержуємо 181 = 52 ・3 + 25; ділимо число 52 на число 25, одержуємо 52 = 25 ・ 2+ 2; ділимо число 25 на число 2, одержуємо 25 = 12 ・ 2 +1; ділимо число 2 на число 1, одержуємо 2 = 1 ・ 2 + 0; одержуємо, що НСД двох чисел 181 і 52 рівний 1.
Тому що НСД не дозволяє встановити чи є число 181 складовим, то продовжуємо виконувати алгоритм Рабіна - Міллера.
3. Послідовно обчислюємо (рис.2.1).
Отже, одержали b = 180 = p - 1. Звідки маємо, що число p = 181 імовірно просте.
Зауваження. Для генерації навіть невеликих простих чисел обчислення досить громіздкі. Тому для реальних чисел, безсумнівно, подібні перевірки чисел на простоту треба робити за допомогою програм на комп'ютері.

Рисунок 2.1 – Обчислення
У літературі дається деяке керівництво при генерації простих чисел для практичних додатків. Це керівництво зводиться до реалізації декількох етапів
(кроків).
1. Згенеруйте випадкове n-бітове число p.
2.
Установіть старший і молодший біти рівними 1. Старший біт у цьому випадку гарантує необхідну довжину простого числа, а молодший – його непарність.
3.
Переконайтеся, що число p не ділиться на малі прості числа 3, 5, 7, 11 і т.д. Найбільш надійна перевірка подільності на всі прості числа, менше 2000.
4.
Виконайте тест Рабіна - Міллера для деякого випадкового числа a.
Якщо p проходить тест, то згенеруйте інше випадкове число a і повторіть тест.
Для практичних додатків досить повторити тест Рабіна – Міллера п'ять разів.
5. Якщо p не проходить один з тестів, треба згенерувати інше число p і повторити дане керівництво знову.
Інше число p, якщо воно виявилося не простим, можна одержати не генеруючи нове, а послідовно перебираючи всі цілі, починаючи від p + 1, p + 2,
і т.д., поки не найдеться просте число.
Перейдемо тепер до питання про генерування великих простих чисел.

Побудова великих простих чисел і детерміновані алгоритми
перевірки чисел на простоту.
Розглянемо ще один спосіб формування простих чисел. Цей спосіб базується на певній процедурі генерування простих чисел, перевірка яких здійснюється за допомогою тестів на простоту.
Такий підхід застосовується, наприклад, у стандарті електронного цифрового підпису (ЕЦП) і базується на наступній теоремі.
Теорема 5. Нехай p = qN + 1, де q – непарне просте число, N – парне число та p < (2q + 1)
2
. Число p є простим, якщо виконуються дві умови:
1) 2
qN
= 1 mod p;
2) 2
N
≠ 1 mod p.
Генерація простого числа з використанням теореми 5 здійснюється по трохи спрощеній в стандарті схемі. Нехай потрібно сформувати просте число p
довжини t ≥ 17 біт. Із цією метою будується убутна послідовність чисел{ti}, де
i = 0, 1, …, s
, для яких t
0
= t, t
i
= [t
i - 1
/2].
Далі послідовно виробляється послідовність простих чисел ps, ps
- 1
, … p
0
, для всіх i = 1, …, s.
Генерація простого числа p
i-1
здійснюється з використанням наступної формули p
i
- 1
= p
i
N
+ 1, де число N задовольняє наступним умовам:· N – парне;
N – таке, що довжина числа p
i - 1
= p
i
N
+ 1 точності поинна дорівнювати t
i - 1
У стандарті дається деякий алгоритм обчислення числа N. Для навчального варіанта N –випадкове парне число, яке одержують за допомогою датчика випадкових чисел (якщо N – непарне, то N = N +1).
Число p
i - 1 уважається отриманим, якщо одночасно виконані наступні дві умови:
1) 2
b
= 1 mod p
i
, b = p
i – 1
N;
2) 2
N
≠ 1 mod p
i
Якщо хоча б одна з умов не виконується, то значення числа N
збільшується на 2, і обчислюється нове значення p
i - 1
, яке знову перевіряється на простоту по двом умовам. Даний процес триває доти, поки не буде отримано просте число p
i - 1
( тобто умови 1 і 2 алгоритму генерації простого числа будуть виконані).
Перевірка чисел Мерсенна на простоту.
Нагадаємо, що число M
s
= 2
s
– 1 (s
≥ 2 – просте число) називається числом
Мерсенна. Критерієм простоти чисел Мерсенна служить наступне твердження.

Теорема. Число Мерсенна M
s
= 2
s
–
1, де s ≥ 3 – непарне число, є простим тоді й тільки тоді, коли
– число s – просте;
– виконується порівняння L
n - 2
≡ 0 mod M
s
, де послідовність {Lk} формується за таким правилом:
L
0
= 4, L
k+1
= (L
2
k
– 2) mod M
s
при k ≥ 0.
2.3
Контрольні запитання та завдання:
1.
Назвіть основні способи генерації простих чисел.
2.
Як проводиться перевірка чисел на простоту в певному числовому діапазоні.
3.
Поясніть як працює тест Міллера-Рабіна.
4.
Поясніть як працює тест Соловея-Штрассена.
5. .
Що таке числа Мерсенна та Кармайкла.
Індивідуальні завдання.
1.
Вивчити алгоритм генерації простих чисел на основі решета
Ератосфена та реалізувати його програмно.
2.
Провести тестування чисел на простоту за допомогою тестів Міллера-
Рабіна та Соловея-Штрассена.