【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明

>>837さんへ
>>607 >>625 >>834 を読んでみてください
すこし改定
---
xの3乗をx^3と書きますね。

(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)^nの係数の計算はFFT高速乗算法を使えばよいのだろう。

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