Ймовірнісний тест на простоту Ферма

Тест базується на теоремі Ферма, яка ствер­джує, що якщо п − просте, то для довільного а, 1 ≤ а ≤ п - 1, має місце рівність a^n-1 ≡ l(mod n). Якщо для заданого n знайдеться хоча б одне таке а, що a^n-1≠ l(mod n), то п не є простим.

Означення. Нехай п − непарне складене число. Число а, 1 < а < п - 1, таке що a^n-1≠ l(mod n), нази­вається свідком Ферма (свідком складеності) для п.

Означення. Нехай п − непарне складене число, а − ціле число, 1 < а < n - 1. Число n називається псевдопростим за основою а, якщо a^n-1 ≡ 1 (mod n). Число а називається брехунцем Ферма (брехунцем простоти) для п. Кількість брехунців Ферма для числа п будемо позначати через fl(n) (Ferma liars).

Наприклад, для довільного складеного n число а = 1 завжди буде брехунцем Ферма, оскільки 1^{n-1 ≡} l(mod n).

АЛГОРИТМ

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

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

1. for i ← 1 to t do

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

   2. Обчислити k ← a^n-1 mod n.

   3. if k ≠ 1 then return («складене»).

2. return(«npocтe»).

Якщо алгоритм дає відповідь «складене», то дійсно число є складеним. Якщо відповідь буде «просте», то або n є дійсно простим, або n є складе­ним, але має велику кількість брехунців. Чим більше значення параметра t, тим більше тестів буде зроб­лено і тим більша ймовірність того, що n є простим.

Приклад. Розглянемо складене число п = 15 та знайдемо його свідки та брехунці Ферма. Для цього складемо таку таблицю:

Свідками Ферма є числа 2, 3, 5, 6, 7, 8, 9, 10, 12, 13. Брехунцями Ферма є числа 1, 4, 11, 14.

Тест Ферма зручно використовувати для пере­вірки числа n на складеність, оскільки для біль­шості натуральних чисел кількість свідків більша за кількість брехунців. Але існують складені чис­ла, які є псевдопростими за довільною основою (взаємно простою з заданим числом). Такі числа називаються числами Кармайкла, і найменше з них дорівнює 561 = 3* 11* 17.

Означення. Число п називається числом Кар­майкла, якщо воно складене та для довільного а, 1 ≤ а≤ n-1, НСД (а, n) = 1, має місце рівність a^n-1 ≡ 1(mod n).

Критерій Корсельта. Для того, щоб складене число n було числом Кармайкла, необхідно і достат­ньо виконання двох умов:

• n не ділиться на квадрат простого числа;

• n - 1 ділиться на р - 1 для всякого простого дільника р числа п.

Приклад 1.

Простими дільниками числа 561 є 3, 11, 17. При цьому жоден з них не входить до розкладу навіть двічі, а число 560 ділиться на 2, 10 та 16:

560 : 2 = 280, 560 : 10 = 56, 560 : 16 = 35.

Твердження. Кожне число Кармайкла є добут­ком хоча б трьох простих чисел.

Приклад 2.

Числа Кармайкла в межах до 100 000:

561, 1105, 1729, 2465, 2821, 6601, 8911,

10 585, 15 841, 29 341, 41 041, 46 657,

52 633, 62 745, 63 973, 75 361.

Теорема (Чернік, 1939). Якщо р = 6т + 1, q = 12т + 1, r = 18m + 1 є простими числами, то число рqr є числом Кармайкла.

Приклад 3.

Якщо покласти m= 1, то отримаємо р = 7, q = 13, r = 19 – всі прості числа. Отже, п = 7 * 13 * 19= 1729 − число Кармайкла.

Кількість чисел Кармайкла у натуральному ряді до 10¹² дорівнює 8241, до 10¹³ − 19279, до 10¹⁴ − 44706, до 10¹⁵− 105212.