Ім'я файлу: Тест на визначення простого числа.pptx
Розширення: pptx
Розмір: 1716кб.
Дата: 12.05.2021
скачати
Пов'язані файли:
3.Доповідь.docx
Тести простотиРозширення: pptx
Розмір: 1716кб.
Дата: 12.05.2021
скачати
Пов'язані файли:
3.Доповідь.docx
План:
Вступ
Тест Фрейма
Тест Міллера – Рабіна
Вступ:
Просте число — це натуральне число, яке має рівно два різних натуральних дільники (лише 1 і саме число).
Тест простоти — алгоритм перевірки, чи є дане число простим.
Тест Ферма
Алгоритм:
Крок 1: Вибрати випадкове число p, та вибрати випадкове число a, що буде меншим за число p.
Крок 2: Знайти найбільший спільний дільник.
Якщо НСД дорівнюватиме 1, переходимо до кроку 3.
Крок 3: Якщо число а в степені p-1 дорівнює 1 по модулю p, то алгоритм перевірив простоту числа. Але існують псевдопрості числа прикладом є число 561, тому даний алгоритм потрібно повторити декілька ра.
Псевдопрості числа
Числа які можуть пройти усі провірки назививають числами Кармайкла
Для прикладу наведемо число 561.
Необхідно проводити провірку декілька раз, адже кількість помилок є надто великою
Тест Міллера - Рабіна
Через існування чисел Кармайкла, яких є безкінечна кількість, необхідно було розробити алгоритм який й б зменшував імовірність проходженням таких чисел тест.
Тест Міллера – Рабіна зменшує цю вірогідність в 4 рази.
Тест Міллера - Рабіна
Алгоритм:
Крок 1: n-1=*m, вводимо дані, та розкладаємо число.
N= число яке перевіряємо.
K= кількість ітерацій.
Крок 2: 1
Крок3: mod n, проводимо потрібну кількість ітерацій.
+1 = число є простим
-1= число є складеним.
Наведемо приклад на числі 3, так як точно знаємо що воно кратне.
Відкривши многочлен отримаємо такий вираз:
Тепер віднявши другий вираз ми отримуємо результат:
Так як в результаті отримуємо числа які є кратні одне до одного, то вважаємо, що число 3 є кратним.
Наведемо інший приклад з числом 4.
При відніманні бачимо, що число 6 не кратне 4, відповідно число 4 не просто
Висновок
Тільки в 2002 другім році був створений тест, що дозволяє точно перевірити число на простоту, та тільки після вдосконалення час виконання став поліміальним, тест хоч і є точним, та все ж по швидкості уступає місце тесту Ферма, який при декількох перевірка є доволі точним, чого вистачає для використання в криптографії.