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

>>77
r=3として例をあげると
x^3は1にしてx^4はxにしてx^5はx^2にしてx^6は1にする。
x^5 +3x^4 +2x^3 +4x^2 +2x +3 ≡
x^2 +3x +2 +4x^2 +2x +3 = 5x^2+5x+5 (mod x^3-1)
これならどんな多項式も2次以下の多項式になる。
だからいつもr次以下の多項式計算だけですむ。
係数の無限長整数変数はr個だけですむ。