Ймовірнісний тест Мілера-Рабіна

Тестом Мілера-Рабіна називається ймовірнісний тест перевірки на простоту, який було запропоно­вано Мілером з використанням ідей Рабіна.

Тест Мілера-Рабіна найбільш часто використо­вується на практиці і називається сильним тестом на простоту. Він базується на такому факті:

Нехай п – непарне просте число, причому п – 1= 2^s r, де r − непарне. Нехай а − таке нату­ральне число, що НСД(а,n) = 1. Тоді має місце одна із рівностей: а^r ≡ 1(mod п) або для деякого j, 0 ≤ j ≤s – 1.

Означення. Нехай п – непарне складене число, п-1 = 2^s r, де r − непарне, а − натуральне число, 1 ≤ а≤ п- 1.

1. Якщо а^r ≠ 1(mod n) та ф для всіх j, 0 ≤ j ≤s – 1, то а називається сильним свід­ком (свідком складеності) для п.

2. Якщо а^r ≡ 1(mod п) або для деякого j, 0 ≤ j ≤s – 1, то а називається сильним брехунцем для п, а само число п - сильним псевдо­простим за основою а. Кількість сильних брехунців числа п будемо позначати через sl(n) (strong liars).

АЛГОРИТМ

Вхід: непарне ціле число п ≥ 3, параметр t ≥ 1.

Вихід: визначення, чи є число п простим.

1. Записати п - 1 = 2^s r, де r − непарне.

2. for i =1 tо t do

1. Обрати довільне ціле а, 2 ≤ а ≤ п - 2.

1. Обчислити y ← а^r (mod п).

2. if y ≠ 1 and y ≠ n – 1 then

j←1

while j ≤ s-1 and y ≠ n-1 do

y←y²mod n

if y =1 then return(«складене»).

j←j+1

if y ≠ n-1 then return(«складене»).

3. return(«просте»).

Приклад 4.

п = 221 = 13 17 − складене число. п - 1 = 220 = 2² 55, s = 2, r = 55.

Нехай а = 5, НСД(5, 221)= 1. a^r(mod n) ≡ 5⁵⁵(mod 221) ≡112 ≠ -1.

Вираз будемо обчислювати для j = 0, 1 (0 ≤ j ≤ 1) поки не отримаємо -1.

j= 0: a^r(mod п) ≡ 5⁵⁵(mod 221) ≡ 112 ≠ -1.

j= 0: a^2r(mod п) ≡ (5⁵⁵)²(mod 221) ≡ 168 ≠ -1, що підтверджує складеність 221.

Нехай а = 21, НСД(21,221) = 1. а^r(mod n) ≡ 21⁵⁵(mod 221) ≡ 200 ≠ 1.

j = 0: a^r(mod п) ≡ 21⁵⁵(mod 221) ≡ 200≠ -1.

j = 1: а^2r(mod n) ≡ (21⁵⁵)²(mod 221) ≡ -1, отже, 221 може бути простим.

Приклад показує, що число 5 є сильним свідком для 221, а 21 є сильним брехунцем для 221.

Якщо перебрати в якості а всі значення від 1 до 220, то можна побачити, що число 221 має 6 таких сильних брехунців: 1, 21,47, 174, 200, 220, а sl(221) = 6.