25-06-2023
Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты.
Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Теоретико-числовые алгоритмы | |
---|---|
Тесты простоты | |
Поиск простых чисел | |
Факторизация |
Перебор делителей • Метод Ферма • P-1 метод Полларда • Ρ-алгоритм Полларда • Метод Лемана • Метод эллиптических кривых (алгоритм Ленстры) • Алгоритм Диксона • Квадратичное решето |
Дискретное логарифмирование | |
Нахождение НОД | |
Арифметика по модулю | |
Умножение чисел |
Тест простоты.