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

>>106 >>78
係数はnで割った余りを格納すればよいので無限長整数でなくても
nが格納できる固定長整数でいい。
nが格納できる固定長整数変数がr個だけでいい。
途中計算は
(x-a)^2,(x-a)^4,(x-a)^8,(x-a)^16,...
と自乗を繰り返すだけだから、
n^2が格納できる固定長整数変数が2r個あればいい。
そして各係数をnで割って余りを出しつつr次以上のm次の係数を
m-r次に加えていけばx^r-1の余りのr次の多項式が得られる。
そして、nを2進展開してその1,0にあわせて
(x-a),(x-a)^2,(x-a)^4,(x-a)^8,(x-a)^16,...
を掛け合わせれば(x-a)^nが得られる。
これをx^r-1で割った余りを係数の足し算で得た後
nで割って余りを出せばよい。
そしてnをrで割った余りの次数のところの係数が1で、
定数項はaで残りの係数は全部0ならよい。