Реферат на тему:
Тести на простоту
Проблема належності заданого натурального числа до класу простих чи
складених чисел є дуже цікавою не тільки в математиці, а й в
комп’ютерних науках. Відрізнити просте число від складеного, а також
розкласти останнє на прості множники є однією з найважливіших задач
арифметики. Пошук великих простих чисел необхідний, наприклад, для
забезпечення надійності систем кодування інформації з відкритим ключем.
Безпека останніх базується на твердженні, що операція множення двох
великих простих чисел є односторонньою функцією.
Для перевірки числа на простоту користуються ймовірносними (Ферма,
Соловай – Штрасена, Мілера – Рабіна) та правдивими тестами.
Ймовірностні тести
Означення. Тест на простоту називається ймовірносним, якщо в результаті
його застосування не можна дати чіткої відповіді на запитання “чи є
задане число простим чи ні?”, але можна виявити часткову інформацію
стосовно простоти.
Наведені нижче тести дають наступну інформацію про непарне ціле число 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
Нашли опечатку? Выделите и нажмите CTRL+Enter
