Головна Головна -> Реферати українською -> Математика -> Тести на простоту

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

Назва:
Тести на простоту
Тип:
Реферат
Мова:
Українська
Розмiр:
22,85 KB
Завантажень:
67
Оцінка:
 
поточна оцінка 5.0


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

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

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

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

Наведені нижче тести дають наступну інформацію про непарне ціле число 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 .

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок