ТЕСТИ ПРОСТОТИ

Тест простоти – це алгоритм, який по заданому натуральному числу визначає, просте воно, чи ні. Найчастіше тести простоти використовують при перевірці чисел на простоту, реалізовуючи їх алгоритми за допомогою комп’ютерних програм. Тому складність алгоритму тесту простоти являється важливою характеристикою будь-якого надалі розглядуваного тесту.

Всі тести простоти можна умовно поділити на такі чотири основні групи: наївні, ймовірнісні, детерміновані та теорико-числові.

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

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

Ймовірнісні тести простоти – це тести простоти, засновані на гнучкому й швидкому алгоритмові перевірки, що мають досить високу погрішність перевірки на предмет простоти. Ймовірнісним тестам характерна висока швидкість обробки даних при перевірці на предмет простоти заданого числа, проте за рахунок цього страждає точність перевірки. Ось загальні характеристики всіх ймовірнісних тестів простоти:

1.     Ймовірнісні тести завжди без помилок визначають просте число.

2.     Ймовірнісні тести не завжди без помилок визначають складене число.

Найпростішим і найрозповсюдженішим являється тест простоти Ферма, заснований на Малій теоремі Ферма. Проте він має занадто велику погрішність.

Детерміновані тести простоти – це тести простоти, алгоритм яких спрямований на безпомилкове визначення заданого числа на простоту, виконуючи мінімум обчислювальних операцій. Детерміновані тести простоти являються великим кроком вперед порівняно з наївними тестами, проте найчастіше являються повною протилежністю ймовірнісним: точність велика, проте складність обчислень також не мала. Все це негативно впливає на швидкість перевірки простоти числа комп’ютером. Саме тому детерміновані тести простоти так і не отримали належної популярності, хоча також трапляються випадки необхідності їх використання. Проте існують і порівняно швидкі детерміновані тести, такі як тест простоти Агравал-Кайал-Саксена. Деякі науковці відносять до детермінованих тестів простоти також і наївні тести, спираючись на їх безпомилкові результати. Особисто я притримуюсь такої ж думки.

Теорико-числові тести простоти – це тести простоти, спрямовані перевіряти числа спеціального вигляду на простоту. З визначення зрозуміло, що певні тести перевіряють на простоту лише окремі числа, що мають зазначений вигляд, наприклад числа Ферма, Мерсенна та ін., на відміну від класичних детермінованих, що перевіряють числа загального натурального вигляду. Але за безпомилковість роботи таких тестів, можна вважати їх відгалуженням детермінованих. Найрозповсюдженішими теорико-числовими тестами простоти являються тест Лукаса-Лемера та тест Профа.