コンピュータによる素因数分解

(1)

コンピュータによる素因数分解

楕円曲線法アノレゴ

P

ズムへの展開について

教科・領域教育専攻自然系(数学)コース広瀬靖弘

はじめに

素因数分解とは，合成数を素数の積に表すことである.近年ではRSA暗号に使用されていて，その信頼性は大きな数の素因数分解の困難さに基づいている.また，楕円曲線暗号の副産物として，楕円関数を使用した素因数分解法である楕円曲線法が 1985年にレンストラによって開発された.楕円曲線法は，暗号にとって大した脅威を与えたわけではない.しかし，予想もしないような斬新な工夫から開発されたことから，素因数分解の劇的な方法が見つかるかもしれないと暗号研究者は関心を寄せている.

研究内容としては，初等整数論，素数判定法，

素因数分解法，コンピュータによる多倍精度計算について挙げられるが，論文では初等整数論から見た楕円曲線法を含む素因数分解法アルゴ、

リズム及びその過程について述べている.

1素因数分解

ユークリッド互除法及び初等整数論の基礎定理について述べている.これらは，素因数分解に欠かせないものである.

初等整委主論の基礎定理合成数nは素数の積に分解される.そこで，同じ素数の積を1つのベキにまとめれば次が成り立つ.

(1)相異なる素数p，q， T，…と α，b， c，…ε Nにより，合成数nは

指導教員丸林英俊

a b

n=p q T.

と表される.

(2)素数 p，q， T，…と対応する指数 a，b， c，

…はnによりIJ填序を除いて一意的に定まる.

2合同式

余りのある割り算の性質を深く追求する為の準備として，合同式を取り扱っている.また，

素数判定法の1つであるフェルマーテストやオイラーの定理は素因数分解法を述べる上で基盤

となるものである.

合同式 n E Nとα，b E

Z

に対して，差。‑

bがnの倍数であるとき aとbはnを法として合同であるといい，

α三 b(mod n) と書き表し，この式を合同式という.

フェノレマーの小定理素数pとaEZに対して，

(1) a^P三 α (modp)

(2) (a， p) = 1 =今aP‑1

= =

1 (mod p) が成り立つ.

フェノレマーテスト (a， n) = 1かつan‑l若1 (mod n)となるGが存在するならば nは合成数

となる.この合成数判定法をフェルマーテストという.これは，フェルマーの小定理の対偶から得られるものである.

A斗A

nHd n べ

U

(2)

オイラーの関数 nENに対して， {L 2， 3，

・，n}の中でnと互いに素となる数の個数を

φ

(n)

で表す.この

φ

をオイラーの関数という.

オイラーの定理 nE N， m =

φ

(n)， (a， n) = 1となる a E Zに対して，

αφ(n) = am三 1(mod n)

が成り立つ n=p=素数のとき

φ か)

=p‑1 であるから，フェルマーの小定理はオイラーの定理に含まれる。

3さまざまな素因数分解法

素因数分解法としてp‑1法，p+1法，楕円曲線法の理論的な展開及びそのアルゴリズムについて述べている.また， UBASICというプログラミング言語を用いて，素因数分解のプログラムを作成している.

p‑l法 1974年，ポラードによって考え出された素因数分解法である.フェルマーテストなどでnが合成数であると分かっているとき n

= pnl (Pは大きな素数)となっていたとしても，

p‑lが小さな素数の積になっていれば，以下のような理論より nの素因数が見つかる可能性があると説明できる.

唱 e今 e

P ‑1 = Pl‑¹P2‑L.

…

^P^r^‑r_や^iMt<M)

となっていると仮定する .

q j < M

^{となるすべて}

の素数に対して

qf<M

^孟^q^F^‑⁺¹となる五を求め，

K = ^I ^I q f

とおく.よって，_p ‑ 1は K の約数である .(a， n)

=

¹^となる ^α^{に対してい，}p)

=

¹^{となるので}

フェルマーの小定理から，

a^K^三 _1(modp)

となる.よって，a^K‑:‑1はpで割り切れる.しかし nでは割り切れないかもしれない.つま

り，

1

<

⁽^a^K^‑ ^L n⁾

<

ⁿ

となる可能性がある.これが成り立てば，nの真の約数は見つかったことになる.そして，真の約数が素数ならば n^{の素因数が見つかった} ことになる.

p‑l法は楕円曲線法の理論の一部に組み込まれている.

p+l法 p‑l法と同様に楕円曲線法の理論に関わっている素因数分解法であるが，実際に p+l法を使用することはほとんどない.

楕円関数微積分でよく知られている式として，

(Z

d

芯

y

諸んゾ τ ^玉 ^吉

^(‑1^~季^{~ç ;i.} ¹⁾

とおくと， y=sin‑ix，つまり x= sin yとなる.

同様に，

r^者 dz

w んぜ

⁽^1‑x²){1 ‑k²:t/1)

とおく.この式を楕円関数という.また，

(0 語~k < 1， ‑1 ~ :t ;;& 1)

x = sn (y， k) = sn y sn (y， 0) = sin y とする.これは，楕円曲線法の元となるものである.

楕円曲線法複数多項式 2次ふるい法と並び，

素因数分解の代表的な方法である.特徴として，

楕円曲線上の点がアーペル群になっていることを利用したものである.また，楕円曲線法は運が良ければ短時間で素因数が見つかるという魅力的な点がある.

﹁﹁

Un y

円六U

コンピュータによる素因数分解