Тестування числа на простоту, ймовірнісні тести
Тестуванням деякого числа a на простоту називається перевірка, є дане число a простим чи ні.
Для цього достатньо перевірити всі можливі прості дільники цього числа, за винятком самого числа a. Така можливість пов’язана з тим фактом у теорії чисел, що будь-яке натуральне число a можна єдиним способом представити у вигляді добутку степенів простих чисел, тобто а = р1к1 * р2к2 *…* рsкs – канонічний розклад числа на прості множники, де - кількість простих чисел, рівних p, присутніх у поданні числа a.
Якщо остача від ділення числа a на деякий можливий простий його дільник рівна нулю, то таке число а не є простим.
Всі можливі прості дільники числа a, які слід перевірити знаходяться в межах від 2 до a div 2. Для великого числа a така перевірка може тривати занадто довго. Тому важливе значення мають різні методи скорочення терміну перевірки.
Проблема визначення належності заданого натурального числа до класу простих чи складених чисел є дуже цікавою не тільки в математиці, а й у комп'ютерних науках. Відрізнити просте число від складеного, а також розкласти останнє на прості множники є однією з найважливіших задач арифметики. Пошук великих простих чисел необхідний, наприклад, для забезпечення надійності систем кодування інформації з відкритим ключем.
Для перевірки чисел на простоту користуються ймовірнісними тестами: Ферма, Соловай-Штрасена, Мілера-Рабіна.
Тест на простоту називається ймовірнісним, якщо в результаті його застосування не можна дати чіткої відповіді на запитання «чи є задане число простим, чи ні?», але можна виявити часткову інформацію стосовно простоти.
Наведені нижче тести дають таку інформацію про непарне ціле число п:
якщо тест визначає, що n є складеним, то це дійсно так;
якщо тест визначає, що n є простим, то зі ймовірністю, близькою до 1, можна вважати, що число є простим.