>>109
はい、言い方を代えるとx^3-1で割った余りの2次式にしているだけですから。
x^5 +3x^4 +2x^3 +4x^2 +2x +3 をx^3-1で割った余りが5x^2+5x+5のはずです。

このうまく工夫されたrを見つけて
a=1から2√r log n まですべてチェックすると
必ず素数判定できる ということ。
このrの見つけ方とaの範囲がうまく押さえられているから
多項式時間でできることがわかった ということだと思うよ。

こちらもまだ全部チェックしているわけではないのでスマソ