Тести на простоту, Детальна інформація

(mod n), то число a називається свідком Ейлера (свідком складеності) для n.

(mod n), то число n називається псевдопростим за основою a. Число a називається брехунцем Ейлера (брехунцем простоти) для n.

Алгоритм

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

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

1. for i \xF0AC 1 to t do

1.1. Обрати довільне ціле a, 2 \xF0A3 a \xF0A3 n – 2.

1.2. Обчислити k \xF0AC a(n-1)/2 mod n.

1.3. if k \xF0B9 1 and k \xF0B9 n – 1 then return (“складене”).

.

1.5. if k \xF0B9 j (mod n) then return (“складене”).

2. return (“просте”).

Тест Мілера - Рабіна

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

Твердження. Нехай n – непарне просте число, при чому n – 1 = 2s * r, де r – непарне. Нехай а – таке натуральне число, що НСД(a, n) = 1. Тоді має місце одна із рівностей:

ar \xF0BA 1 (mod n)

або

\xF0BA -1 (mod n) для деякого j, 0 \xF0A3 j \xF0A3 s - 1

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

\xF0B9 -1 (mod n) для всіх j, 0 \xF0A3 j \xF0A3 s – 1, тоді а називається сильним свідком (свідком складеності) для n.

\xF0BA -1 (mod n) для деякого j, 0 \xF0A3 j \xF0A3 s – 1, тоді а називається сильним брехунцем для n, а само число n – сильним псевдопростим за основою а. Кількість сильних брехунців числа n будемо позначати через sl(n) (strong liars).

Алгоритм

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

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

1. Записати n – 1 = 2s * r, де r – непарне.

2. for i = 1 to t do

2.1. Обрати довільне ціле a, 2 \xF0A3 a \xF0A3 n – 2.

2.2. Обчислити y \xF0AC ar (mod n).

2.3. if y \xF0B9\xF0201 and y \xF0B9 n - 1 then

j \xF0AC 1