Реферат Тести на простоту Проблема належності заданого натурального числа до класу простих чи складених чисел є дуже цікавою не тільки в матем


СкачатиСкачать (DOC|ZIP):
Тести на простоту Проблема належності заданого натурального

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

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

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

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

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

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

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


СкачатиСкачати: Тести на простоту Проблема належності заданого натурального


Схожі реферати:
  • Чи можна підприємцю обійтися без ризику (реферат)
  • Галактики різних видів. Зорі, чорні діри, холодні об'єкти (рефеарт)
  • Ринок мінеральної та солодкої води в Україні Реферат з РПС Донедавна ринок мінеральної та солодкої води був одним із так
  • Рембрандт Харменс ван Рейн (1606-1669) (реферат)
  • Політичний маркетинг (реферат)
  • Африка – Україна (реферат)
  • РЕФЕРАТ на тему: "Підприємництво та споживач. Невід ємні права споживача та напрямки їх реалізації" Закон України Про з
  • Формування готовності викладачів та студентів до використання НІТ в медичному навчальному закладі Провів
  • Правове регулювання орендних відносин у сучасному законодавстві України (дипломна)
  • Характеристика художніх стилів МКЅЅ-МКЅЅЅ ст. Мистецтво і література МКЅЅ-МКЅЅЅ ст. кожної з європейських країн відзначаються неповторною своєрідністю. Але сам




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.031285