Тест простоти - алгоритм, який по заданому натуральному числу визначає, просте чи це число. Розрізняють детерміновані і імовірнісні тести.

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


Загальні тести простоти


Спеціалізовані тести простоти

Література




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