Тести на простоту, Детальна інформація

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

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

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

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

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

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

Наведені нижче тести дають наступну інформацію про непарне ціле число n:

Якщо тест визначає, що n є складним, то це дійсно так.

Якщо тест визначає, що n є простим, то з ймовірністю, близькою до 1, можна вважати, що число є простим.

Тест Ферма

Тест базується на теоремі Ферма, яка стверджує, що якщо n – просте, то для довільного a, 1 \xF0A3 a \xF0A3 n - 1 має місце рівність an-1 \xF0BA 1 (mod n). Якщо для заданого n знайдеться хоча б одне таке a, що an-1 \xF0B9 1 (mod n), то n не є простим.

Означення. Нехай n – непарне складене число. Число a, 1 \xF0A3 a \xF0A3 n – 1, таке що an-1 \xF0B9 1 (mod n), називається свідком Ферма (свідком складеності) для n.

Означення. Нехай n – непарне складене число, a – ціле число, 1 \xF0A3 a \xF0A3 n – 1. Число n називається псевдопростим за основою a, якщо an-1 \xF0BA 1 (mod n). Число a називається брехунцем Ферма (брехунцем простоти) для n.

Очевидно, що для довільного складеного n число a = 1 завжди буде брехунцем Ферма, оскільки 1n-1 \xF0BA 1 (mod n).

Алгоритм

Вхід: непарне ціле число n \xF0B3 3, параметр t \xF0B3 1.

Вихід: визначення, чи є чило n простим.

1. for i \xF0AC 1 to t do

1.1. Обрати довільне ціле a, 2 \xF0A3 a \xF0A3 n – 2.

1.2. Обчислити k \xF0AC an-1 mod n.

1.3. if k \xF0B9 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