Огляд алгоритмів пошуку і розпізнавання простих чисел, інформація про їх застосовності. Куріцин Михайло Люлькова Олена Сизов Ілля
Просте число просте число - це натуральне число, яке має рівно два різних натуральних дільники: одиницю і самого себе. Решта числа, крім одиниці, називаються складовими. Послідовність простих чисел починається так: 2, 3, 5, 7, 11, 13, 17, 19, 23. 29, 31, ... 3
Алгоритми пошуку простих чисел Прості способи знаходження початкового списку простих чисел аж до деякого значення дають. Решето Ератосфена Решето Сундарама Решето Аткіна 6
7 Решето Ератосфена Алгоритм: Нехай p = 2 (першому простому числу). Вважаючи від р, кроками по р, закреслити в списку все числа від 2р до n. Знайти Перший не закреслена число, більше ніж p, і привласнити значення змінної p це число. Повторювати кроки 3 і 4 до тих пір, поки p не стане більше ніж n. Прості числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Решето Ератосфена Складність алгоритму: 8 O (n. 2. 2 (??))
Решето Сундарама 9 Алгоритм: З ряду натуральних чисел від 1 до N виключаються всі числа виду i + j + 2ij (i = 1,2. ..., 2 ?? + 1? 1 2; j = i, i + 1, .... 2 ?? + 1). Кожне з решти чисел множиться на 2 і збільшується на 1. Отримана в результаті послідовність являє собою всі непарні прості числа в відрізку [1,2N + 1]. i = 1, j = 1, ..., 6; i = 2, j = 1,2,3; Прості числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.
Решето Сундарама. Обгрунтування Алгоритм працює з непарними натуральними числами великими 1, представленими у вигляді 2m + 1, де m є натуральним числом. Якщо число 2m + 1 є складовим, то воно представляється у вигляді добутку двох непарних чисел великих одиниці, тобто: 10 2m + 1 = (2i + 1) (2j + 1). де i, j - натуральні числа m = 2ij + i + j Що еквівалентно: Якщо з ряду натуральних чисел виключити всі числа виду 2ij + i + j. то для кожного з решти чисел m число 2m + 1 має бути простим. Якщо число 2m + 1 є простим, то число m неможливо уявити у вигляді 2ij + i + j і, таким чином, m буде уважно в процесі роботи алгоритму.
Решето Аткіна B основу алгоритму "решета Аткіна" покладені три стандартні теореми теорії елементарних чисел: 11 n - просте, якщо: 4. 2 +. 2 =. (??> 0.> 0) n mod 4 = 1 n - непарне число n - просте, якщо: 3. 2 +. 2 =. (??> 0.> 0) n mod 6 = 1 n - непарне число n - просте, якщо: 3. 2. 2 =. (??> 0.> 0) n mod 12 = 11 n - непарне число 1. 2. 3.
Алгоритм Створити решето (масив відповідності простих чисел для всіх позитивних, цілих чисел починаючи з 2). Спочатку всі елементи решета позначаються як складові. Для кожного числа n в решеті. якщо залишок від ділення по модулю 60: Рівний 1, 13, 17, 29, 37, 41, 49, або 53, і n = 4 * x2 + y2 поміняти значення в решеті на протилежне. Дорівнює 7, 19, 31, або 43, і n = 3 * x2 + y2; поміняти значення решеті на протилежне. Дорівнює 11, 23, 47, або 59, і n = 3 * x2 - y2 при (x> y); поміняти значення в решеті на протилежне. (Х і у цілі, позитивні числа) Взяти найменше число з решета, позначене як просте, і позначити всі елементи решета, кратні квадрату цього простого числа як складові. Повторити крок 3, 12
Решето Аткіна Алгоритм має асимптотичну складність: 13. (. Log log.) І вимагає наступне кількість біт пам'яті: O (. 1 2 + ?? (1))
Cравненіе алгоритмів пошуку простих чисел 14
Алгоритми розпізнавання простих чисел. Тести простоти Тест простоти - алгоритм, який по заданим натуральним числом визначає, просте чи це число. Перебір дільників Теорема Вільсона Тест Ферма Тест Пепина Тест Міллера - Рабина Тест Агравал - Каяла - Сакса 15
Перебір дільників перебір подільників - алгоритм тестування простоти числа шляхом повного перебору всіх можливих потенційних подільників. 16 Алгоритм: Перебір всіх цілих чисел від 2 до квадратного кореня з числа n і обчислення залишку від ділення n на кожне з цих чисел. Якщо залишок від ділення на деяке число m дорівнює нулю, то m є дільником n. У цьому випадку або n оголошується складовим, і алгоритм закінчує роботу. Після досягнення квадратного кореня з n і неможливості скоротити n ні на одне з менших чисел, n оголошується простим.
Теорема Вільсона Теорема Вільсона - теорема теорії чисел, яка стверджує, що 17 p - просте число тоді і тільки тоді, коли (p. 1)! + 1 ділиться на p
Тест Ферма Заснований на теоремі Ферма, в якій мовиться: 18 Якщо p - просте число, то для будь-якого цілого a виконується рівність. 1? 1 (.) Або (. 1? 1) ділиться на. остачі. Для складових p істинність рівності малоймовірна. Примітка:
Тест Пепина Тест Пепіно є тестом простоти для чисел Ферма. Число ферма - це число виду. = 2 2. +1. - ціле, невід'ємне. Число Ферма є простим тоді і тільки тоді, коли. (.) /. (.). На сьогоднішній день відомо лише 5 простих чисел Ферма: 3, 5, 17, 257 і 65537. 19
Тест Міллера - Рабина Тест Міллера - Рабина - імовірнісний поліноміальний тест простоти. Тест дозволяє ефективно визначати, чи є дане число складовим. Однак, з його допомогою можна строго довести простоту числа. 20 Свідки простоти і теорема Рабина Нехай m - непарне число більше 1. Тоді m-1 представимо у вигляді: m-1 = 2. * t. де t - непарній Ціле число a, 1 Тест Міллера - Рабина 21 Алгоритм: Параметром алгоритму Міллера - Рабина є кількість раундів r. У кожному раунді виконуються наступні дії: Вибирається випадкове число a, 2
Тест Міллера - Рабина Складність алгоритму. 22 O (. 3.) Однак, правильність роботи алгоритму не завжди є доведеною. Імовірність, що складене число не буде виявлено за час t, зазвичай не перевищує. Тест Агравал - Каяла - Сакса (або тест AKS) Універсальність: тест AKS може використовуватися для перевірки простоти будь-яких чисел. Поліноміальний: Найбільше час роботи алгоритму обмежена поліномом від кількості цифр в перевіряється числі. Детермінізм: Алгоритм гарантує отримання відповіді. Безумовність: Коректність тесту AKS не залежить від будь-яких недоведених гіпотез. 23 Тест Агравал - Каяла - Сакса (або тест AKS) Основні ідеї та принципи, на якому заснований алгоритм AKS: 24 n - просте тоді і тільки тоді, коли: НСД (a, n) = 1 (.). (.) (.) Теорема AKS Нехай. 2 ;. ціле ;. прості числа. причому. 1,2. НСД. = 1 q - найбільший простий дільник (r-1). 4. 2. (. 1) /. 1. 1,2, ..., 2. 2. +1. 1 Тоді n - ступінь простого числа. затвердження: Тест Агравал - Каяла - Сакса (або тест AKS) Складність алгоритму AKS: 26 O (. 19.) Примітка: Вираз. 1. означає наступне: для многочленів (.). і. знайдеться многочлен. (Кільце многочленів від x з цілими коефіцієнтами) такий, що всі коефіцієнти многочлена (.). 1. кратні. Порівняння тестів простоти 27 Дякую за увагу! 29