AKS素数判定法

ウィキペディア

AKS素数判定法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/11/24 03:55 UTC 版)

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