Adleman–Pomerance–Rumely primality test とは

計算理論では、Adleman-Pomerance-Rumely primality検定は、数が素数かどうかを判断するためのアルゴリズムです。この目的のための他のより効率的なアルゴリズムとは異なり、乱数の使用を避けるため、確定的素数検定です。発見者、Leonard Adleman、Carl Pomerance、Robert Rumelyにちなんで命名されています。このテストには、円環状フィールドの算術演算が含まれます。
その後、APR-CLと呼ばれるHenri CohenとHendrik Willem Lenstraによって改良されました。それは時間の整数nの素数性をテストできます:
( ln n ) O ( ln ln ln n ) . {\displaystyle (\ln n)^{O(\ln \,\ln \,\ln n)}.}