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

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

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

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


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

 
 

Цікаве