背景

ある識別子を生成する時に素因数分解の一意性が使えることを知ったのでメモ
ただし、現実的には数が大きくなりすぎるため、利用はできないので注意
トップの画像はなんとなくペンローズの三角形にした

素因数分解の性質

素因数分解の一意性とは

定義は次になる。

全ての正の整数は素数の積として一意に表せる。

当たり前と言えば当たり前という定義。
なぜなら、素因数分解すれば全部素数になるため。

素因数分解の一意性の証明

数学的帰納法と背理法を組み合わせて素因数分解の一意性の証明をする。

準備
- まず、任意の自然数 $n > 1$は少なくとも1つの素因数を持つことを仮定する
背理法の適用
- 素因数分解の一意性が成り立たないと仮定し、矛盾を導く
仮定
- ある自然数$n$が2つの異なる（一意ではない）素因数分解を持つと仮定する
- $n = p₁ \times p₂ \times … \times pₖ = q₁ \times q₂ \times … \times qₘ$
- ここで、$pᵢ$と$qⱼ$はすべて素数で、$k ≤ m$ とする
最小の反例の考察
- $n$を、この性質を持つ最小の数とする
- つまり、$n$を「2つの異なる素因数分解を持つ最小の数」と仮定
素因数の比較
- $p₁ ≤ q₁$ とする（そうでない場合は順序を入れ替える）
割り算の考察
- $\frac{n}{p₁}$ を考える
- これは$n$より小さい数
矛盾の導出
- もし$p₁ < q₁$の場合
  - $\frac{n}{p_1}$は自然数になる（なぜなら、$p_1$は$n$の約数のため）
  - $\frac{q₁ \times q₂ \times … \times qₘ}{p_1}$では$p_1$はどの$q_m$とも異なる為、自然数にはならない
  - つまり、等式が成り立たず矛盾となる
- もし$p₁ = q₁$の場合
  - $\frac{n}{p₁} = p₂ \times … \times pₖ = q₂ \times … \times qₘ$ となる
  - $\frac{n}{p_1}$は$n$より小さい自然数になり、このnより小さい数も、「2つの異なる素因数分解を持つ」ことになる
  - しかし、 $n$は「2つの異なる素因数分解を持つ最小の数」であると仮定している
  - したがって、 $n$より小さい数がそのような性質を持つことは矛盾する
結論
- どちらの場合も、$\frac{n}{p₁}$ が矛盾する
- これは$n$が最小の反例であるという仮定に矛盾する
Q.E.D.
- したがって、最初の仮定（素因数分解の一意性が成り立たない）が誤りであることが示された
- つまり、素因数分解の一意性が証明された

まとめると、背理法で、「素因数分解の一意性」の命題の逆として「異なる2つの素因数分解がある」と仮定を立て、そして「2つの異なる素因数分解を持つ最小の数」として条件を満たすのかを考察した。結果、等式に矛盾や、反例の条件を満たさなかった。故に、条件は矛盾するので、仮定が成り立たない。それを反例として逆説的に命題が成り立つ事を証明した。

素因数分解の困難性とは

非常に大きな合成数を素因数分解することは、現在の計算能力では現実的な時間内には不可能と考えられている
その理由は、素数の分布には規則性がなく、ある数の素因数分解をするには、試行錯誤的に探索して探す必要があるため

素因数分解の応用のアイディア

データ圧縮

データを素因数分解し、その結果を保存することで、元のデータをよりコンパクトに表現する
ある整数を素因数分解した結果を保存する方が、元の整数を保存するよりも少ない情報量で済むかもしれないため

識別子の生成

IDが大きくなりすぎるため、現実的ではないが、素因数分解の一意性で、n番目のネットワークのm番目のホストに一意にIDを振る事が可能。

$$ id = 2^n \times 3^m $$

2と3が素数ではなくても、互いに素ならいけるはず。
また下のように逆変換もできる。

$$ 3888= 2^4 \times 3^5 $$

RSA暗号

RSA暗号とは

RSA暗号は公開鍵暗号方式で使われ、公開鍵で暗号化し、秘密鍵を持つ者のみが復号できる方法
素因数分解の性質が使われている暗号方式

RSA暗号の仕組み

素因数分解の一意性よりは、素因数分解問題の困難性を利用しているが、よく使われるRSA暗号の仕組みは以下になる。

鍵生成:
- 2つの大きな素数 $p$ と $q$ を選び、それらの積 $n = p \times q$ を計算する
- $n$は公開鍵の一部として公開される
- $p$と$q$ は秘密鍵として厳重に保管される
指数の生成:
- まず、$\phi(n)= (p-1)(q-1)$を計算する
- $\phi(n)$はオイラーのφ関数であり、非公開
- その後2つの指数を計算する
1. 公開指数 $e$
  - $e$は暗号化に使用される公開指数
  - $e$は$\phi(n)$と互いに素である数
  - 通常、小さな素数（例：3, 17, 65537など）が選ばれる
2. 秘密指数 $d$
  - $d$は復号に使用される秘密指数
  - $d$は$e$のモジュラ逆数として計算される
  - $e \times d ≡ 1 \pmod {\phi(n)}$
  - つまり、$d \times e$ を $\phi(n)$で割った余りが1になるようなdを見つける
暗号化:
- 送信者は、公開鍵 $n$ と公開鍵の一部である公開指数 $e$ を使って、平文 $m$ を暗号文 $c$ に変換する $$c \equiv m^e \pmod{n}$$
復号:
- 受信者は、秘密鍵 $p$ と $q$ から計算される秘密指数 $d$ を使って、暗号文 $c$ を平文 $m$ に変換する $$m \equiv c^d \pmod{n}$$

$e$と$d$の関係は、暗号化と復号が互いに逆操作になることを保証する。

数学的には$(m^e)^d ≡ m^{e \times d} \equiv m \pmod n$となっている
その証明にはオイラーの定理や中国剰余定理が使われている
暗号化された後に復号された message は元の message と同じになる

つまり次が言える。

RSA暗号の安全性の根拠は、大きな合成数 $n$ を素因数分解することが非常に難しいという点にある
$p$ と $q$ が分からなければ、秘密指数 $d$ を計算することが困難であり、暗号文を復号することができないから

オイラーの定理による証明

$(m^e)^d ≡ m^{e \times d} \equiv m \pmod n$の証明。

todo

その他

モジュロ演算の例

70が法（modulus）で合同（congruent ）になるモジュロ（modulo）演算の例。

$$ 74 \equiv 2401 \equiv 4 \pmod{70} $$

モジュラ逆数

モジュラ逆数は、モジュラ演算（剰余演算）における「逆数」の概念。

数$a$のモジュロ$m$におけるモジュラ逆数$b$とは、次の条件を満たす数:

$$ a \times b \equiv 1 \pmod m $$

つまり、$a$と$b$の積を$m$で割った余りが$1$になるような$b$のこと。

重要な特性:

モジュラ逆数が存在するのは、$a$と$m$が互いに素（最大公約数が$1$）の場合のみ
存在する場合、モジュラ逆数は $0$ から $m-1$ の範囲内に唯一存在する

モジュラ逆数の例

modulo $7$における$3$のモジュラ逆数:

$$ 3 \times 5 = 15 \equiv 1 \pmod 7 $$

したがって、3のモジュロ7におけるモジュラ逆数は5。

オイラーのφ関数

オイラーのφ関数とは、ある整数$n$に対して、$n$と素な自然数の個数（$\phi(n)$）を返す関数。
$n$が互いに素な2つの素数$p$と$q$の積である場合、$(p-1)(q-1)$で求められる。

$$ \phi(n) = (p-1)(q-1) $$

つまり、ある素数pに対して、pとp以下の整数で互いに素な素数の個数は以下になる。

$$ \phi(p) = p - 1 $$

例えば、素数$p=11$の、11未満の正の整数は、1, 2, 3, 4, 5, 6, 7, 8, 9, 10 の10個。
したがって、$\phi(11)=(11-1)=10$、なので、素数なので当たり前だが10個。

オイラーのφ関数の例

$n=6$のオイラーのφ関数の例。

$$ \phi(6) = (2-1)(3-1) = 2 $$

自然数$1, 2, 3, 4, 5, 6$の中で、$n$と互いに素なのは$1$と$5$
故に、$\phi(6)=2$となる

なお、互いに素ではなく、かつ素数でもない数に対しては素因数分解をするしかない。

剰余演算の性質

剰余演算には以下の便利な性質があり、計算途中の値が大きくなりすぎる事を防げる。

$$ a\times b \pmod n ≡ (a\mod n) \times (b\mod n) \pmod n \\ a ^ b \pmod n ≡ (a\mod n) ^ b \pmod n $$

つまり、基数と指数は大きな数でも分解可能という事。

繰り返し二乗法

RSA暗号では冪剰余の計算が必要になが繰り返し二乗法などのアルゴで簡単に計算ができる
繰り返し二乗法は、効率的にべき乗を計算するためのアルゴリズムで、シンプルに指数法則で分解する方法
つまり、冪剰余の計算の容易性という事である

指数を2進数に変換
- 13を2進数で表すと1101となる
2のべき乗の計算
- $7^1$, $7^2$, $7^4$, $7^8$を計算 $$ 7^1 = 7 \\ 7^2 = 7^1 \times 7^1 = 49 \\ 7^4 = 7^2 \times 7^2 = 2401 \\ 7^8 = 7^4 \times 7^4 = 5764801 $$
積を求める
- 2進数表現の1が立っている桁に対応するべき乗の積を計算する $$ 7^13 = 7^8 \times 7^4 \times 7^1 \\ = 5764801 \times 2401 \times 7 = 96889010407 $$

実際は剰余演算の性質を利用して、次のように途中でモジュロ計算を行い結果を出す。

$$ 7^{13} \equiv 7^8 \times 7^4 \times 7^1 \\ \equiv 21 \times 21 \times 7 \\ \equiv 7 \pmod{70} $$

まとめ

データ圧縮や識別子に素因数分解の一意性を利用するのは、無限のリソース空間がない限り無理だろう
素因数分解の困難性は、RSA暗号の基盤になっている

素因数分解の一意性と困難性

目次

背景