このページに関してのお問い合わせはこちら
暗号総崩れ-素数判定が多項式時間で可能
ツイート
114
:
デフォルトの名無しさん
:
02/08/09 22:50
>>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の範囲がうまく押さえられているから
多項式時間でできることがわかった ということだと思うよ。
こちらもまだ全部チェックしているわけではないのでスマソ