AKS素数判定法

読み方、または別称：

-そすうはんていほう

AKS素数判定法とは

AKS素数判定法（-そすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 n が素数であるかどうかを判定するのにかかる時間が\log(n) の多項式を上界とすることをいう。n の多項式ではないことに注意する必要がある。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ AKS素数判定法の改定履歴 ]