暗号総崩れ-素数判定が多項式時間で可能

(x-1)^2= x^2 -2x +1 で1次の項が2で割り切れる。
(x-1)^3= x^3 -3x^2 + 3x -1 で1次と2次の項の係数が3で割り切れる。
(x-1)^4= x^4 -4x^3 + 6x^2 -4x +1 は2次の項の係数6は4で割り切れない。
4は素数ではない。
(x-1)^5= x^5 -5x^4 + 10x^3 -10x^2 +5x -1 の1次から4次の項の
係数はすべて5で割り切れる。

nを与えられたらnと互いに素な数aを取って
多項式(x-a)^nの1次から(n-1)次までの係数がすべてnで割り切れて
a^nをnで割った余りがaならばnは素数

でもこのやりかたではn次の多項式の係数を計算しなければならず大変
よって小さい数rをうまくとって
x^rは1とする計算を間に入れてr次の多項式の計算に収めればよい。
このrの候補の取り方が最初のwhile文。
このrは小さい数ですむ というのがLemma4.2の主張。
チェックaの候補もrが小さいので少しの候補ですむ。

r次以下の多項式(x-a)^rの係数の計算はFFTを使えばよいのだろう。

8ページ目には予想として、この判定は
このaは1だけのチェックでよく、
rはn^2-1の約数ではないという条件だけでよいのではないか
といっている。