Тести на простоту (реферат)

Реферат на тему:

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

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

Ймовірностні тести

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

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

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

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

Тест Ферма

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

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

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

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

Алгоритм

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

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

1. for i to t do.

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

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

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

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

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

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

a.
a14 mod 15.

a.
a14 mod 15.

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

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

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

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

an-1 (mod n).

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

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

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

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

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

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

Приклад. Числа Кармайкла в межі до 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). Якщо p = 6m + 1, q = 12m + 1, r = 18m + 1 є простими числами, то число pqr є числом Кармайкла.

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

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

C (n) — {1 + o (1)} log log log n / log log n.

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

Доведення. Нехай yp = $$\frac{b^{2p}-1}{b^2-1}$$, де p — непарне просте число, НСД (p, b2 — 1) = 1. Тоді yp = $$\frac{b^p-1}{b-1}\frac{b^p+1}{b+1}$$ — складене непарне ціле число. Враховуючи що b2p — 1 ділиться на $$\frac{b^{2p}-1}{b^2-1}$$, то b2p (mod yp).

yp — 1 = $$\frac{b^{2p}-1}{b^2-1}$$ — 1 = $$\frac{b^{2p}-1-b^2+1}{b^2-1}$$ = b2 $$\frac{b^{2p-2}-1}{b^2-1}$$ = b2 $$(b^{p-1}+1)$$ $$\frac{b^{p-1}-1}{b^2-1}$$ .

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

Отже $$b^{y_p-1}$$ = $$(b^{2p}{)}^{\frac{y_p-1}{2p}}$$ (mod yp).

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

Приклад. Нехай b = 2, p = 5. Тоді y5 = $$\frac{2^{\text{10}}-1}{2^2-1}$$

= 341 = 11 * 31.

.

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

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

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

$$a^{\frac{n-1}{2}}$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(an) (mod n).

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

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

1. Якщо НСД (a, n) > 1 або $$a^{\frac{n-1}{2}}$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(an) (mod n), то число a називається свідком Ейлера (свідком складеності) для n.

2. Якщо НСД (a, n) = 1 та $$a^{\frac{n-1}{2}}$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(an) (mod n), то число n називається псевдопростим за основою a. Число a називається брехунцем Ейлера (брехунцем простоти) для n.

Алгоритм

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

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

1. for i to t do.

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

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

1.3. if k and k — 1 then return («складене»).

1.4. Обчислити символ Якобі j math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(an) .

1.5. if k (mod n) then return («складене»).

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

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

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

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

ar (mod n).

або.

$$a^{2^{j}r}$$ (mod n) для деякого j, 0 — 1.

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

1. Якщо ar (mod n) та $$a^{2^{j}r}$$ (mod n) для всіх j, 0 — 1, тоді а називається сильним свідком (свідком складеності) для n.

2. Якщо ar (mod n) або $$a^{2^{j}r}$$ (mod n) для деякого j, 0 — 1, тоді а називається сильним брехунцем для n, а само число n — сильним псевдопростим за основою а. Кількість сильних брехунців числа n будемо позначати через sl (n) (strong liars).

Алгоритм

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

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

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

2. for i = 1 to t do.

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

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

2.3. if y 1 and y — 1 then.

j /p>

while j — 1 and y — 1 do.

y mod n.

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

j + 1.

if y — 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) 7 (mod 29) 1.

Вираз $$a^{2^{j}r}$$ будемо обчислювати для j = 0, 1 (0 поки не отримаємо -1.

j = 0: ar (mod n) 107 (mod 29) -1.

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

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

ar (mod n) 7 (mod 29) 1.

j = 0: ar (mod n) 197 (mod 29) -1.

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

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

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

ar (mod n) 5 (mod 221) 2 1.

Вираз $$a^{2^{j}r}$$ будемо обчислювати для j = 0, 1 (0 поки не отримаємо -1.

j = 0: ar (mod n) 555 (mod 221) 2 -1.

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

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

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

ar (mod n) 55 (mod 221) 0 1.

j = 0: ar (mod n) 2155 (mod 221) 0 -1.

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

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

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

Твердження. Нехай n — непарне складене число. Тоді якщо 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) = / 4.

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

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

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

Істині тести

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

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

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

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

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