Тест на простоту Адлемана – Померанса – Рамли - Adleman–Pomerance–Rumely primality test

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

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

${\ Displaystyle О ((\ журнал п) ^ {\ журнал \, \ журнал \, \ журнал п}).}$

Программные реализации

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

использованная литература

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

Эта статья, посвященная алгоритмам или структурам данных, является незавершенной . Вы можете помочь Википедии, расширив ее .

• v
• т
• е

Эта статья по теории чисел незавершена . Вы можете помочь Википедии, расширив ее .

• v
• т
• е