UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваТести на простоту (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1730
Скачало414
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

складених чисел є дуже цікавою не тільки в математиці, а й в

комп’ютерних науках. Відрізнити просте число від складеного, а також

розкласти останнє на прості множники є однією з найважливіших задач

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

забезпечення надійності систем кодування інформації з відкритим ключем.

Безпека останніх базується на твердженні, що операція множення двох

великих простих чисел є односторонньою функцією.

 

Для перевірки числа на простоту користуються ймовірносними (Ферма,

Соловай – Штрасена, Мілера - Рабіна) та правдивими тестами.

 

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

 

Означення. Тест на простоту називається ймовірносним, якщо в результаті

його застосування не можна дати чіткої відповіді на запитання “чи є

задане число простим чи ні?”, але можна виявити часткову інформацію

стосовно простоти.

 

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

оскільки для більшості натуральних чисел кількість свідків більша за

кількість брехунців. Але існують складені числа, які є псевдопростими за

довільною основою (взаємно простою з заданим числом). Такі числа

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ