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

Тести на простоту

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

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

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

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

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

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

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

Тест Ферма

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

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

Означення. Нехай n – непарне складене число, a – ціле число, 1 ? a ? n –
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 ? a ? n – 2.

1.2. Обчислити k ? an-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.

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

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

an-1 ? 1 (mod n)

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

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

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

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

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

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

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

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

Теорема (Чернік, 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 –
19279, до 1014 – 44706, до 1015 – 105212. З іншого боку декількома
авторами наводилася верхня межа для C(n) – кількість чисел Кармайкла від
1 до n. Одна з них (і яка на сьогодні вважається найбільш точною):

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

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

, то b2p ? 1 (mod yp).

.

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

? 1 (mod yp).

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

= 341 = 11 * 31.

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

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

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

(mod n)

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

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

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

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

Алгоритм

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

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

1. for i ? 1 to t do

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

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

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

.

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

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

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

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

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

ar ? 1 (mod n)

або

? -1 (mod n) для деякого j, 0 ? j ? s — 1

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

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

? -1 (mod n) для деякого j, 0 ? j ? s – 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 ? a ? n – 2.

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

2.3. if y ??1 and y ? n — 1 then

j ? 1

while j ? s – 1 and y ? n – 1 do

y ? y2 mod n

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

j ? j + 1

if y ? 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) ? 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) = ?(n) / 4 = (3 – 1) * (5 – 1) / 4 = 2 * 4 / 4 = 2.

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

Істині тести

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

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

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

. Числа, що залишаться в ряду після операцій викреслення, є простими.

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

Похожие записи