■きょうおぼえたこと

"滑らかな整数"という物があるらしい（意味が分からない）

ネットで調べ物するときは重くてもPDF開いた方が良い

一部のはてな記法

gcdは最大公約数

pow(a,b)はaのb乗

mod(a,b)はaをbで割ったときの余り

N=pq (p,qは素数)を因数分解するには

｛1,2,…,N-1｝から適当にgcd(a,N)=1となるaを取る

aのNを法とした位数rを求める

aのNを法とした位数rを求めるには

f(x)=mod(pow(a,x),n)

としてf(x+kr)=f(x)となるrを求める（kは任意の自然数？）

rが偶数になるまでaを取るとこからやり直す

(偶数じゃないと下の式のpow()が整数にならないから)

p=gcd(pow(a,r/2)+1,N)

q=gcd(pow(a,r/2)-1,N)

p,qのいずれかがNでなければそれらが求めたい因数

らしい

で、rを求めるところがイマのコンピュータだと大変で、

Shorさんのアルゴリズムは量子PCでソレが出来てスゴイらしい

Permalink | 記事への反応(1) | 18:15

ツイートシェア