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

(1)

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

ふるい

( s i e v e )

系のアルゴリズム

ス

攻一

専コ育 ) 教学域数領 ( 享

・系

科然上教自村

はじめに

初等整数論の基本定理に基づき，長年にわたり素因数分解法が研究され実践されてきた.この分野の研究は，コンビューターによる演算能力の発達に伴い， 1970年代より盛んに研究が進められてきた.その以前でも理論は確立されていたが，

従来の計算法は物理的な限界を持っていたので，

実際に大きな自然数の素因数分解を示すことは困難を極めていた.今ある素因数分解法の発展は，

古くからの理論の積み重ねと，最新の演算処理技術によって支えられている.そして，その発展の根幹には，現在の研究に至るまでに考案されてきた様々な方法があることを忘れてはならない.

素因数分解法の発展には大きく分けて2つの流れがある.ひとつは『群論系』の流れで，その名のとおり群論的手法が利用されている.ここでは詳しく取り上げないが，既約剰余群を利用したp

‑ 1法や，近年研究の可能性が注目されている楕円曲線法などが，この代表的な方法としてあげられる.この楕円曲線法は， RSA暗号と並んで暗号理論の分野でも応用されている.

もう一方の流れは『ふるい

( s i e v e )

系』と呼ばれるもので，フェルマ一法から発展していったものであるといえる.フェルマ一法とは， Lehman が1974年に提案した方法で，中学校で扱う初歩的な因数分解を利用したものである.一見単純だが極めて効果的な素因数分解法であるといえるだろう.このフェルマー法に様々なアイデアを盛り込むことによって，従来の試行割算法より効率的な方法が次々と提案された.

ここでは後者のふるい系について取り上げ，古典的な方法から比較的新しい複数多項式2次ふるい法まで、を流れを追って示すこととする.また，

現在最高速のアルゴ、リズムである一般数体ふるい法，そしてLehman予想の仮説を用いない世界初のアノレゴリズムであるA K S判定法，この分野の最先端である2つの理論についても紹介する.

指導教員

丸林英俊

1

初等整数論からの準備

本論文で活用する初等整数論の基本的用語および定理を述べている.

。定義(素数) 自然数nに対して， :t 1と土n 以外の約数を真の約数という.真の約数をもっn を合成数といい n*lかっ真の約数をもたない nを素数という.つまり，正の約数が3個以上なら合成数 2個ならば素数というわけで、ある. 1 個しかない 1は特別扱いして，合成数とも素数と

も考えない.

定理(素因数分解と分解の一意性)

合成数nは素数の積に分解される.また，その分解の仕方は素数のJI慎序を除いては一意的である.

定理1.1 5 (ブエノレマーの小理) 素数pと整数aに対しては

①a^P^三 a (mod p)

②(a， p)=1 斗 a(p‑l)三 1 (mod p) が成り立つ.

2 古典的素数判定方法試行割算法

試行割算法とは

r

nが自然数かつ合成数であれば nはF nより大きくない素因数pをもって

し1るJという定理を用いている.小さい素数から順にわっていき nを割り切る素因数を見つけるという最も素朴な方法である.極めて小さい素因数を見つけるのに有効な方法である.

エラトステネスのふるい

( E r a t o s t h e n e s 'S i e v e )

素数の研究には，あらかじめ素数を調べておき，

それらを表にした素数表を作っておくと便利である.素数か否か，また特定範囲の素数の分布も調べることができる.たいへん素朴な方法であるが，

いまでも素数表を効率よく作るには，この方法しかないようだ¥

‑ 400‑

(2)

3

確率的素数判定法

素数判定法の中には，与えられた自然数nを

「合成数であるJまたは「良く分からなしリと判別するアルゴリズムがある.この判定法を確率的素数判定法(probabilistic primality test)とし1

うことがある.これに対して「素数である」あるいは否と判定するアルゴリズムは決定的素数判定法(deterministicprimality test)という.次のフェルマ一法は代表的な確率的素数半Ij定法で、ある.

ブエノレマー法

フェルマーの小定理の対偶をとることで，次の結果が得られる.

(a， n)

=

1 かっ a (n‑

l ) 手

1 (mod n) となる整数aが存在すれば nは合成数である.

すなわち，あるnが与えられたとき， (a， n)=

1となる aに対してa(n‑l)を計算し，それがnを法として 1と合同でなければ nはただちに合成数であることが分かる.このような合成数判定法をフェルマーテストといいこの操作を複数回重ねて行うことで素数を確率的に判定する方法をフェルマー法という.

4 ふるい ( s i e v e ) 系の素因数分解

ふるい(sieve)系の素因数分解は，フェルマー法から発展していったものである.中学校で扱う初歩的な因数分解を利用したものであるが，極めて効果的な素因数分解法であるといえるだろう.

このフェルマ一法に様々なアイデアを盛り込むことによって，従来の試行割算法より効率的な方法が次々と提案された.

基本原理一般にnの素因数分解には X2三 y2 (mod n)

となる x，yを見つければよい.当然だが，最初からx三士yとすればこの合同式は得られるが無意味である.

X_i^三 Yi (mod n) かつ科学Yi

となる X_i' Yiを集めて組み合わせて平方数を作る.そして， mod nでの代表元を異なるようにとって，その分解の違いを利用するのである.

く平方数作成> たくさんの整数 r0' r

l'

… .

しが与えられたとき

・まず適当な個数の素数の集合{p_1'P2' . . ， PB}

を決める.

次にその集合に属する素数のみで因数分解できてしまうものをsmoothな数という.つまり

Yi

= T I

^P^j^e(i.^j)

となる Y_iをB+l個さがす.これらをあらためて r0' r l' • . ，. r Bとおく.

これらのべき指数部分に注目し，さらにそれをmod2で考えて次のような (2/22上の) B次元ベクトルにする.

V i= (e (i， 1) mod 2， e (i， 2) mod 2，...， e i(， B) mod 2) 自明でない関係式を求める.

C_OV_O+C₁V₁

+ ・・・

_+CBVB^三

o

(mod 2) 元に戻した式は平方数である.

直筆量

発想、・・・分解したいnに対して 1，2，3，... にnを加えて代表元を変える.

定数倍法

発想・・・分解したいnに対して， n/2の近くの数を 2倍してnを引けば代表元がずれる.

連分数法 (ContinuedFraction Method)

発想・・・ベル方程式より得られる式を利用すれば，求めたい平方数をつくることができる.

2次ふるい法(Quadratic Sieve)

発想・・・分解したい奇数nに対して， F nの近くの数を2乗してnを引けば代表元がずれる.

複数多項式2次ふるい法(MultiplePolynomial Quadratic Sieve)

発想・・・ 2次ふるい法と原理は同じだが 2 次式を複数利用することで，より効率的に求める

ことができる.

数体ふるい法(NumberField Sieve)

発想・・・代数方程式の複素数体での解を

e

， mod nでの解をM，とすると 0とM の式はmod

nで異なる代表元を与える.

A K S判定法

発想・・・特定の定義に基づき，十分にたくさんのパラメーターについての合同式を確かめれば，

素数性を厳密に判定することができる. (これは自明ではないが，証明できる. )

‑401 ‑

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