Критерий простоты Адлемана – Померанса – Румели

В вычислительной теории чисел тест Адлемана -Померанса-Румели на простоту представляет собой алгоритм определения того, является ли число простым . В отличие от других, более эффективных алгоритмов для этой цели, он избегает использования случайных чисел, поэтому представляет собой детерминированный тест на простоту . Он назван в честь своих первооткрывателей Леонарда Адлемана , Карла Померанса и Роберта Румели . Тест включает в себя арифметику в круговых полях .

Позже он был улучшен Анри Коэном и Хендриком Виллемом Ленстра , обычно называемый APR-CL . Он может проверить простоту целого числа n во времени:

${\displaystyle (\log n)^{O(\log \,\log \,\log n)}.}$

Реализации программного обеспечения

• UBASIC предоставляет реализацию под названием APRT-CLE (расширенный APR Test CL).
• Апплет факторинга, использующий APR-CL при определенных условиях (исходный код включен)
• Pari/GP условно использует APR-CL в своей реализации isprime().
• mpz_aprcl — это реализация с открытым исходным кодом, использующая C и GMP.
• LLR Жана Пенне использует APR-CL в некоторых типах простых тестов в качестве запасного варианта.

Рекомендации

• Адлеман, Леонард М .; Померанс, Карл ; Румели, Роберт С. (1983). «Об отличии простых чисел от составных чисел». Анналы математики . 117 (1): 173–206. дои : 10.2307/2006975. JSTOR  2006975.
• Коэн, Анри ; Ленстра, Хендрик В. младший (1984). «Проверка простоты и суммы Якоби». Математика вычислений . 42 (165): 297–330. дои : 10.2307/2007581 . hdl : 1887/2136 . JSTOR  2007581.
• Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации . Биркхойзер. стр. 131–136. ISBN 978-0-8176-3743-9.
• АПР и АПР-CL