>>89
nを入力とするとき、nの桁数（=O(log(n)）の多項式で
抑えられるのが多項式時間。

実行時間が sqrt(n) だと O(exp(log(n)))なので指数時間。