>>108
なぜｘがlog n なのかというと、もともと
素因数分解の判定問題が判定したい数 n の桁数
に対して多項式時間で解けるかという問題を考えて
いるからです。