2つの例：因数分解とGCD

今日存在する古典コンピューターは非常に高速であり、その速度はますます向上しているように見えます。 このため、コンピューターはあらゆる計算問題を解けるほど高速だと思い込む人もいるかもしれません。

しかし、この考えは誤りです。 一部の計算問題は本質的に非常に複雑であり、解くアルゴリズムは存在するものの、今日地球上のいかなるコンピューターも、それほど大きくない入力に対してさえ、人間の一生どころか地球の寿命以内にそのアルゴリズムを実行し終えるほど高速ではありません。

さらに詳しく説明するために、整数因数分解問題を紹介しましょう。

整数因数分解

入力：整数 $N\geq 2$
出力：$N$ の素因数分解

$N$ の素因数分解とは、$N$ の素因数と、それらを掛け合わせて $N$ を得るために各素因数を何乗すべきかのリストを意味します。 例えば、$12$ の素因数は $2$ と $3$ であり、$12$ を得るには $2$ の $2$ 乗と $3$ の $1$ 乗の積を取ります。

$$12 = 2^2 \cdot 3$$

素因数の順序を除き、各正整数 $N\geq 2$ に対して素因数分解はただ1通りです。これは算術の基本定理として知られる事実です。

整数因数分解およびこの議論に関連する他の概念をさらに説明するために、Pythonでの簡単なコードデモンストレーションがいくつか役に立ちます。これらのデモンストレーションには以下のインポートが必要です。

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

PythonのSymPy記号数学パッケージの factorint 関数は、選択した任意の入力 $N$ に対して整数因数分解問題を解きます。例えば、12の素因数分解を求めると、当然ながら上記の因数分解と一致します。

N = 12
print(factorint(N))

{2: 2, 3: 1}

$12$ のような小さな数の因数分解は簡単ですが、因数分解する数 $N$ が大きくなると、問題はより困難になります。 例えば、はるかに大きな数に対して factorint を実行すると、一般的なパソコンでも短いながらも体感できる遅延が生じます。

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

さらに大きな $N$ の値に対しては、少なくとも現時点でわかっている限り、問題は不可能なほど困難になります。 例えば、1991年から2007年にかけてRSA研究所が実施したRSA因数分解チャレンジでは、10進数で309桁（2進数で書くと1024ビット）の以下の数を因数分解すれば$100,000の懸賞金が提供されました。 この数に対する賞金は受け取られることなく、その素因数は今も不明のままです。

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

RSA1024に対して factorint を実行する手間は省いて構いません。私たちの生涯では終わらないでしょう。

大きな整数を因数分解するための最も高速な既知のアルゴリズムは数体篩として知られています。 このアルゴリズムの使用例として、10進数で250桁（2進数で書くと829ビット）のRSAチャレンジナンバーRSA250が、2020年に数体篩を用いて因数分解されました。 この計算には数千CPUコア年を要し、世界中の数万台のマシンに分散して実施されました。 ここではその解を確認することで、この成果の偉大さを実感できます。

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

RSA公開鍵暗号システムのセキュリティは整数因数分解の計算困難性に基づいており、整数因数分解の効率的なアルゴリズムが存在すればそれを破ることができます。

次に、関連していますが全く異なる問題、すなわち2つの整数の最大公約数（GCD）を計算することを考えましょう。

最大公約数（GCD）

入力：非負整数 $N$ および $M$（少なくとも一方は正）
出力：$N$ と $M$ の最大公約数

2つの数の最大公約数とは、両方を割り切る最大の整数です。

この問題はコンピューターで容易に解くことができます。計算コストは2つの入力数の乗算とほぼ同じです。 Pythonの math モジュールの gcd 関数は、RSA1024よりもはるかに大きな数の最大公約数をまたたく間に計算します。（実際、この例の2つの数の最大公約数がRSA1024です。）

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

これが可能なのは、GCDを計算するための非常に効率的なアルゴリズムが存在するためです。最も有名なのは2,000年以上前に発見されたユークリッドのアルゴリズムです。

RSA1024のような大きな数をまたたく間に因数分解できる、まだ発見されていない高速アルゴリズムが存在する可能性はあるでしょうか？ 答えはイエスです。 GCDを計算するユークリッドのアルゴリズムと同様にシンプルでエレガントな効率的因数分解アルゴリズムが今までに発見されていないことは不思議に思えるかもしれませんが、今日まで見つかっていないという事実以外に、整数因数分解の非常に高速な古典アルゴリズムの存在を否定するものは何もありません。 明日発見される可能性もあります。しかし、あまり期待しない方がよいでしょう。 何世代もの数学者とコンピューター科学者が探し続けており、RSA1024のような数の因数分解は依然として私たちの手の届かないところにあります。