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

while j \xF0A3 s – 1 and y \xF0B9 n – 1 do

y \xF0AC y2 mod n

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

j \xF0AC j + 1

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

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

Твердження. Якщо a – сильний брехунець числа n, то a буде брехунцем Ейлера для числа n.

Приклад. n = 29 – просте число. n – 1 = 28 = 22 * 7. s = 2, r = 7.

Нехай а = 10, НСД(10, 29) = 1.

ar (mod n) \xF0BA 107 (mod 29) \xF0BA 17 \xF0B9\xF0201.

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

j = 0: ar (mod n) \xF0BA\xF020107 (mod 29) \xF0BA 17 \xF0B9\xF020-1.

j = 1: a2r (mod n) \xF0BA\xF020\xF028107)2 (mod 29) \xF0BA -1, 29 може бути простим.

Нехай а = 19, НСД(19, 29) = 1.

ar (mod n) \xF0BA 197 (mod 29) \xF0BA 12 \xF0B9\xF0201.

j = 0: ar (mod n) \xF0BA\xF020197 (mod 29) \xF0BA 12 \xF0B9\xF020-1.

j = 1: a2r (mod n) \xF0BA\xF020\xF028197)2 (mod 29) \xF0BA -1, 29 може бути простим.

Приклад. n = 221 = 13 * 17 – складне число. n – 1 = 220 = 22 * 55. s = 2, r = 55.

Нехай а = 5, НСД(5, 221) = 1.

ar (mod n) \xF0BA 555 (mod 221) \xF0BA 112 \xF0B9\xF0201.

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

j = 0: ar (mod n) \xF0BA\xF020555 (mod 221) \xF0BA 112 \xF0B9\xF020-1.

j = 1: a2r (mod n) \xF0BA\xF020\xF028555)2 (mod 221) \xF0BA 168 \xF0B9\xF020-1, що підтверджує складеність 221.

Число 5 є сильним свідком для 221.

Нехай а = 21, НСД(21, 221) = 1.

ar (mod n) \xF0BA 2155 (mod 221) \xF0BA 200 \xF0B9\xF0201.

j = 0: ar (mod n) \xF0BA\xF0202155 (mod 221) \xF0BA 200 \xF0B9\xF020-1.

j = 1: a2r (mod n) \xF0BA\xF020\xF0282155)2 (mod 221) \xF0BA -1, 221 може бути простим.

Число 21 є сильним брехунцем для 221, а 221 є сильним псевдопростим за основою 21.

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