vchilka.in.ua 1

ТЕСТИ НА ПРОСТОТУ


Проблема належності заданого натурального числа до класу простих чи складених чисел є дуже цікавою не тільки в математиці, а й в комп’ютерних науках. Відрізнити просте число від складеного, а також розкласти останнє на прості множники є однією з найважливіших задач арифметики. Пошук великих простих чисел необхідний, наприклад, для забезпечення надійності систем кодування інформації з відкритим ключем. Безпека останніх базується на твердженні, що операція множення двох великих простих чисел є односторонньою функцією.

Для перевірки числа на простоту користуються ймовірносними (Ферма, Соловай – Штрасена, Мілера - Рабіна) та правдивими тестами.


ЙМОВІРНОСНІ ТЕСТИ



Означення. Тест на простоту називається ймовірносним, якщо в результаті його застосування не можна дати чіткої відповіді на запитання “чи є задане число простим чи ні?”, але можна виявити часткову інформацію стосовно простоти.


Наведені нижче тести дають наступну інформацію про непарне ціле число n:

  • Якщо тест визначає, що n є складним, то це дійсно так.

  • Якщо тест визначає, що n є простим, то з ймовірністю, близькою до 1, можна вважати, що число є простим.



Тест Ферма


Тест базується на теоремі Ферма, яка стверджує, що якщо n – просте, то для довільного a, 1  an - 1 має місце рівність an-1  1 (mod n). Якщо для заданого n знайдеться хоча б одне таке a, що an-1  1 (mod n), то n не є простим.

Означення. Нехай n – непарне складене число. Число a, 1  an – 1, таке що an-1  1 (mod n), називається свідком Ферма (свідком складеності) для n.



Означення. Нехай n – непарне складене число, a – ціле число, 1  an – 1. Число n називається псевдопростим за основою a, якщо an-1  1 (mod n). Число a називається брехунцем Ферма (брехунцем простоти) для n.

Очевидно, що для довільного складеного n число a = 1 завжди буде брехунцем Ферма, оскільки 1n-1  1 (mod n).

Алгоритм


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

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

1. for i  1 to t do

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

1.2. Обчислити kan-1 mod n.

1.3. if k  1 then return (“складне”).

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


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


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


a

1

2

3

4

5

6

7

a14 mod 15


1

4

9

1

10

6

4




a

8

9

10

11

12

13

14

a14 mod 15

4

6

10

1

9

4

1


Свідками Ферма є числа 2, 3, 5, 6, 7, 8, 9, 10, 12, 13.

Брехунцями Ферма є числа 1, 4, 11, 14.


Позначимо через F(n) множину брехунців числа Ферма:

F(n) = {a  Zn | an-1  1 (mod n)}

Тоді

|F(n)| = .


Приклад. Дільниками n = 15 будуть 3 та 5. Кількість його брехунців дорівнює

|F(15)| = НСД(14, 2) * НСД(14, 4) = 2 * 2 = 4.

З вище наведеного прикладу маємо: F(15) = {1, 4, 11, 14}.

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



Означення. Додатнє складене число n називається числом Кармайкла, якщо для кожного a, 1  an – 1, має місце рівність: ana (mod n).


Якщо n – число Кармайкла, то для довільного a, 1  an – 1, для якого НСД(a, n) = 1, має місце рівність:

an-1  1 (mod n)


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


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

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



Доведення.

Необхідність. Маємо: n | ana для всіх a. Доведемо, що n є вільним від квадратів та з p | n випливає p – 1 | n – 1.

Якщо n не є вільним від квадратів, то воно має деякий нетривіальний дільник a2. Тобто a2 | n | ana. Але звідси випливає a2 | ana, або a | an-1 – 1, чого не може бути.

Нехай p | n, a – генератор мультиплікативної групи Zp. a має порядок p – 1 та ap-1  1 (mod p). Тоді p | n | a * (an-1 – 1). Оскільки a < p, то p не ділить a. Звідси p повинно ділити an-1 – 1, тобто an-1  1 (mod p). Оскільки p – 1 – найменша степінь a, для якої ap-1  1 (mod p), але ми маємо an-1  1 (mod p), то n – 1 повинно ділитися на p – 1.


Достатність. Маємо число n, вільне від квадратів, яке задовольняє умові: p | np – 1 | n – 1. Необхідно довести, що n | ana для всіх a.

Відомо, що число a, вільне від квадратів ділить число b тоді і тільки тоді, коли кожен із простих дільників a ділить число b. Отже нам достатньо довести, що p | ana для всіх простих p що ділять n (p | n), або те ж саме що an-1  1 (mod p) (a  0). Але враховуючи що p – 1 | n – 1, рівність можна замінити на ap-1  1 (mod p), яка є вірною, оскільки це – мала теорема Ферма.


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

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


Наменшим числом Кармайкла є 561, яке було знайдене самим Кармайклом у 1910 році. В [1] показано, що кількість чисел Кармайкла нескінченна, причому в натуральному ряді від 1 до n їх не менше ніж n2/7.


Приклад. Наступними за 561 числами Кармайкла будуть:

1105 = 5 · 13 · 17    (4 | 1104, 12 | 1104, 16 | 1104),

1729 = 7 · 13 · 19    (6 | 1728, 12 | 1728, 18 | 1728),

2465 = 5 · 17 · 29    (4 | 2464, 16 | 2464, 28 | 2464),

2821 = 7 · 13 · 31    (6 | 2820, 12 | 2820, 30 | 2820),

6601 = 7 · 23 · 41    (6 | 6600, 22 | 6600, 40 | 6600),

8911 = 7 · 19 · 67    (6 | 8910, 18 | 8910, 66 | 8910),


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


Приклад. Числа Кармайкла в межі до 100000:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.



Приклад. Найменшими числами Кармайкла з k = 3, 4, , ..., 9 простими множниками будуть:


k

 

3

561 = 3 · 11 · 17

4

41041 = 7 · 11 · 13 · 41

5

825265 = 5 · 7 · 17 · 19 · 73

6

321197185 = 5 · 19 · 23 · 29 · 37 · 137

7

5394826801 = 7 · 13 · 17 · 23 · 31 · 67 · 73

8

232250619601 = 7 · 11 · 13 · 17 · 31 · 37 · 73 · 163

9

9746347772161 = 7 · 11 · 13 · 17 · 19 · 31 · 37 · 41 · 641


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


Приклад. Якщо покласти m = 1, то отримаємо p = 7, q = 13, r = 19 – всі прості числа. Отже n = 7 * 13 * 19 = 1729 – число Кармайкла. Перевірено, що при m  100 лише для m = 1, 6, 35, 45, 51, 55, 56, 100 отримуються числа Кармайкла.


Теорема. Позначимо через C3(x) кількість чисел Кармайкла, менших x, які мають в точності 3 простих множника. Тоді для великих x має місце оцінка:

C3(x) = O(x5/14 + O(1))

Доведення. Якщо n є числом Кармайкла з трьома простими множниками p, q, r (2 < p < q < r), то n - 1  0 (mod p - 1), n - 1  0 (mod q - 1), n - 1  0 (mod r - 1).


Нехай g = НСД(p - 1, q - 1, r - 1) та a, b, c такі що p – 1 = g * a, q – 1 = g * b, r – 1 = g * c, a < b < c. Звідси gbc + b + c 0 mod a, gac + a + c  0 mod b, gab + a + b 0 mod c. Оскільки a, b, c є взаємно простими, то ці три конгруенції можна замінити однією: g * (a * b + a * c + b * c) + a + b + c 0 mod (a * b * c). Це вірно, оскільки з того що НСД(a, b, c) = 1 та c  0 mod НСД(a, b), b  0 mod НСД(a, c), a  0 mod НСД(b, c) випливає НСД(a, b) = НСД(a, c) = НСД(b, c) = 1. Отже якщо відомі a, b, c, то можна визначити g за модулем a * b * c.

Будемо рахувати кількість N четвірок (g, a, b, c), що задовольняють вище описаним умовам та нерівності g3 * a * b * cx. Таким чином C3(x) N. Запишемо N = N1 + N2 + N3, де N1 – кількість четвірок (g, a, b, c), для яких g > a * b * c, N2 – кількість четвірок (g, a, b, c), для яких G < ga * b * c, G = x3/14, N3 – кількість четвірок (g, a, b, c), для яких g  G та ga * b * c.

Оцінка N1.


Означення. Узагальнені числа Кармайкла. Нехай k  Z. Множину чисел

Ck = {n N: min(n, n + k) > 1, an+ka (mod n) для всякого a N}


будемо називати узагальненими числами Кармайкла k – го порядку.


Таким чином усі звичайні числа Кармайкла разом із усіма простими числами будуть належити до C0.


Теорема. Узагальнений критерій Корсельта. Нехай k  Z. Тоді число n належить Ck тоді і тільки тоді, коли

1) n > max(1, 1 – k);

2) n є вільним від квадратів;

3) p – 1 | n + k – 1 для всіх простих p, що ділять n.


Лема. Для всіх k, n  Z наступні умови еквівалентні:

а) p – 1 | n + k – 1 для всіх простих p, що ділять n.

б) p – 1 | n / p + k – 1 для всіх простих p, що ділять n.

Доведення. Нехай p – просте, p | n, m = n / p. Тоді

p – 1 | m * p + k – 1 p – 1 | m * p + p * (k – 1) – (p – 1) * (k – 1)

p – 1 | m * p + p * (k – 1)  p – 1 | m + k – 1

Остання еквівалентність має місце, оскільки p – просте.


Лема. Якщо n  Ck, то n – вільне від квадратів.

Доведення. Нехай p2 | n для деякого простого p. Тоді p2 | n | pn+kp, звідки p2 | pn+kp, або p | pn+k-1 – 1, що неможливо.

Теорема. Якщо число q вибрано довільним чином, то ймовірність того що воно просте, асимптотично дорівнює 1 / log q. Якщо відомо, що обране довільним чином число q не ділиться на p, то ймовірність його простоти збільшується на множник p / (p – 1).



Наприклад, ймовірність того що p = 6m + 1 є простим для деякого обраного навмання m, дорівнює (2 / 1 * (3 / 2) * 1 / log(6m + 1) = 3 / log(6m + 1), оскільки заздалегідь відомо що 6m + 1 не ділиться ані на 2, ані на 3.


Річард Пінч, провівши велику кількість обчислень, виявив, що кількість чисел Кармайкла у натуральному ряді до 1012 дорівнює 8241, до 1013 – 19279, до 1014 – 44706, до 1015 – 105212. З іншого боку декількома авторами наводилася верхня межа для C(n) – кількість чисел Кармайкла від 1 до n. Одна з них (і яка на сьогодні вважається найбільш точною):

C(n)  n1 – {1 + o(1)} log log log n / log log n


Теорема (Чіполла, 1904). Існує нескінченно багато складених псевдопростих чисел за основою b.

Доведення. Нехай yp = , де p – непарне просте число, НСД(p, b2 – 1) = 1. Тоді yp = – складене непарне ціле число. Враховуючи що b2p – 1 ділиться на , то b2p  1 (mod yp).

yp – 1 = – 1 = = b2 = b2 .


Оскільки yp – 1 - парне, а також за теоремою Ферма bp-1  1 (mod p) (вираз bp-1 - 1 ділиться на p), то yp – 1  0 (mod 2p).

Отже =  1 (mod yp).

Всі числа yp є псевдопростими за основою b.


Приклад. Нехай b = 2, p = 5. Тоді y5 = = 341 = 11 * 31.

Оскільки 2340 1 (mod 341), то складене число 341 є псевдопростим за основою 2.


Тест Соловай - Штрасена


Тест Соловай – Штрасена базується на критерії Ейлера: якщо n – просте, то

(mod n)

для всіх значень a, для яких НСД(a, n) = 1.


Означення. Нехай n – непарне складене число, a – ціле число, 1  an – 1.

1. Якщо НСД (a, n) > 1 або (mod n), то число a називається свідком Ейлера (свідком складеності) для n.

2. Якщо НСД (a, n) = 1 та (mod n), то число n називається псевдопростим за основою a. Число a називається брехунцем Ейлера (брехунцем простоти) для n.


Алгоритм


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

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

1. for i  1 to t do

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

1.2. Обчислити ka(n-1)/2 mod n.

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

1.4. Обчислити символ Якобі j.

1.5. if kj (mod n) then return (“складене”).

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


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



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


Лема. Якщо n = 1 + 2s * r, де r – непарне, то

an-1 – 1 = (ar – 1) * (ar + 1) * (a2*r + 1) * … * ( + 1)

Доведення індукцією по s. При s = 0 вираз є істиним. Нехай розклад на множники є вірним для s = k. Тоді при s = k + 1 маємо:

an-1 – 1 = – 1 = ( – 1) * ( + 1 ),

що вірно.

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


ar  1 (mod n)

або

 -1 (mod n) для деякого j, 0  js - 1

Доведення. Оскільки має місце розклад

an-1 – 1 = (ar – 1) * (ar + 1) * (a2*r + 1) * … * ( + 1),

а при простому n за теоремою Ферма ліва частина обертається в 0, то і права частина також повинна дорівнювати 0. Тобто мати місце одна із рівностей, наведених в умові теореми.


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

1. Якщо ar  1 (mod n) та  -1 (mod n) для всіх j, 0  js – 1, тоді а називається сильним свідком (свідком складеності) для n.

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

Алгоритм


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

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

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


2. for i = 1 to t do

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

2.2. Обчислити yar (mod n).

2.3. if y 1 and yn - 1 then

j  1

while j s – 1 and yn – 1 do

yy2 mod n

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

jj + 1

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

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


Твердження. Якщо число n після t циклів тесту Мілера – Рабіна дає відповідь “просте”, то ймовірність того що n є дійсно простим, дорівнює 1 - .


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


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

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

ar (mod n)  107 (mod 29)  17 1.

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

j = 0: ar (mod n) 107 (mod 29)  17 -1.

j = 1: a2r (mod n) 107)2 (mod 29)  -1, 29 може бути простим.


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

ar (mod n)  197 (mod 29)  12 1.

j = 0: ar (mod n) 197 (mod 29)  12 -1.

j = 1: a2r (mod n) 197)2 (mod 29)  -1, 29 може бути простим.



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

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

ar (mod n)  555 (mod 221)  112 1.

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

j = 0: ar (mod n) 555 (mod 221)  112 -1.

j = 1: a2r (mod n) 555)2 (mod 221)  168 -1, що підтверджує складеність 221.

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


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

ar (mod n)  2155 (mod 221)  200 1.

j = 0: ar (mod n) 2155 (mod 221)  200 -1.

j = 1: a2r (mod n) 2155)2 (mod 221)  -1, 221 може бути простим.

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


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


Твердження. Нехай n – непарне складене число. Тоді якщо n  9, то кількість його сильних брехунців не більша за (n) / 4.


Твердження. Нехай n = p * q – добуток двох простих чисел, d = НСД(p - 1, q - 1). Тоді кількість брехунців числа n дорівнює

sl(n) = r2 * (2 + (4t – 4) / 3),

де d = 2t * r, r – непарне.

Приклад. n = 221 = 13 * 17. d = НСД(12, 16) = 4 = 22 * 1, r = 1, t = 2.


sl(221) = 12 * (2 + (42 – 4) / 3) = 2 + 4 = 6.


Твердження. Нехай n = p * q – добуток двох простих чисел, p = 2 * r + 1, q = 4 * r + 1, r – непарне. Тоді кількість брехунців досягає своєї верхньої межі:

sl(n) = (n) / 4


Приклад. При r = 1 маємо: p = 3, q = 5, n = p * q = 15.

sl(15) = (15) / 4 = (3 – 1) * (5 – 1) / 4 = 2 * 4 / 4 = 2.

Число 15 дійсно має двох сильних брехунців.


ІСТИНІ ТЕСТИ



Означення. Тест на простоту називається істиним, якщо в результаті його застосування можна однозначно встановити, чи є задане число простим чи ні.

Решето Ератосфена


Найпростіший метод встановлення як простоти так і складеності числа був відомий ще у давнину і називається він решетом Ератосфена:

Виписати в ряд числа від 2 до n. Перше число в ряду є простим. Викреслити з ряду числа, які є кратними 2. Далі взяти друге число, що стоїть в ряду і викреслити всі числа, кратні йому. І так далі брати і-те число та викреслювати кратні йому числа поки i < . Числа, що залишаться в ряду після операцій викреслення, є простими.


Цей метод є ефективним коли число n невелике (n < 10.000.000.000). При цьому його можна використовувати не тільки для тестування на простоту, а й для пошуку простих чисел у вказаному інтервалі та для розв’язку задачі факторизації.


Теорема Вільсона (1770)

Число n є простим тоді і тільки тоді, коли n | (n – 1)! + 1.

n


(n – 1)! + 1

2

2

3

3

5

25

7

721



ЛІТЕРАТУРА

1. W.R.Alford, A.Granville and C.Pomerance. There are many Carmichael numbers, Ann. Math. 140 (1994), 703-722.