WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Тести на простоту - Реферат

Тести на простоту - Реферат

Ейлера: якщо n - просте, то
(mod n)
для всіх значень a, для яких НСД(a, n) = 1.
Означення. Нехай n - непарне складене число, a - ціле число, 1 a n - 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 a n - 2.
1.2. Обчислити k a(n-1)/2 mod n.
1.3. if k 1 and k n - 1 then return ("складене").
1.4. Обчислити символ Якобі j .
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. Якщо ar 1 (mod n) та -1 (mod n) для всіх j, 0 j s - 1, тоді а називаєтьсясильним свідком (свідком складеності) для n.
2. Якщо ar 1 (mod 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 дійсно має двох сильних брехунців.
Істині тести
Означення. Тест на простоту називається істиним, якщо в результаті його застосування можна однозначно встановити, чи є задане число простим чи ні.
Решето Ератосфена
Найпростіший метод встановлення як простоти так і складеності числа був відомий ще у давнину і називається він решетом Ератосфена:
Виписати в ряд числа від 2 до n. Перше число в ряду є простим. Викреслити з ряду числа, які є кратними 2. Далі взяти друге число, що стоїть в ряду і викреслити всі числа, кратні йому. І так далі брати і-те число та викреслювати кратні йому числа поки i < . Числа, що залишаться в ряду після операцій викреслення, є простими.
Цей метод є ефективним коли число n невелике (n < 10.000.000.000). При цьому його можна використовувати не тільки для тестування на простоту, а й для пошуку простих чисел у вказаному інтервалі та для розв'язку задачі факторизації.
Loading...

 
 

Цікаве