>>100
計算量はO(√n)
√n=exp(1/2 * log n)だからlog nの指数

xの多項式は
a_0 + a_1 x + a_2 x^2 + ... + a_n x^n
であなたのいうとおり。
多項式時間の多項式とは、nの桁数を表すlog n について多項式ということ。
a_0 + a_1 log n + a_2 (log n)^2 + ... + a_n (log n)^m
は(log n)^mのオーダー O((log n)^m)

でO((log n)^12)でできる素数判定が書いてあるみたい