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

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

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

$(\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