📖

従来の暗号技術を支える数学

に公開
math
暗号
公開鍵暗号
共有鍵暗号
idea

はじめに

現在広く利用されている暗号技術は、量子コンピュータの登場によって安全性が揺らぐ可能性があると指摘されています。
この問題への解決策として二つのアプローチが注目を集めています。
一つは、量子コンピュータでも解けない計算問題に基づいた「耐量子計算機暗号（PQC）」 です。
もう一つは、量子力学の原理を利用する「量子暗号（QKDなど）」 です。

私はこれらの最先端の暗号技術に強い関心があり、独学で得た知識を体系的に整理するために、記事シリーズとしてまとめています。

本記事では、その中でも従来の暗号技術の安全性を保証してきた数学的基盤に焦点を当てて整理します。

RSA暗号、ElGamal暗号、そして楕円曲線暗号といった公開鍵暗号の安全性はそれぞれ、素因数分解問題、離散対数問題、楕円曲線離散対数問題といった、解くのに膨大な時間がかかる「数学的に困難な問題」 によって守られています。

ここでは、これらの「困難な問題」がどのように暗号方式の安全性を保証しているのかを解説します。さらに、これらの数学の壁を脅かす解読手法についてもご紹介します。

また、暗号技術を深く理解するための参考として、その基盤となる数学的構造や性質（群・環・体・位相・フェルマーの小定理など） についても触れています。

なお、従来の暗号方式である公開鍵暗号方式と共通鍵暗号方式の仕組みや応用、さらには次世代の暗号として注目されている格子問題、およびそれを採用したML-KEM(PQC（耐量子計算機暗号）の一種) について知りたい方は、以下の記事もあわせてご覧ください。

RSA暗号：素因数分解の困難性を利用した公開鍵暗号方式

RSA暗号は、現在広く利用されている代表的な公開鍵暗号方式です。

安全性の根拠
RSA暗号の安全性は、二つの大きな素数を掛け合わせてできた合成数を、元の素数に分解する(素因数分解)ことが極めて難しいという数学的な困難性に基づいています。

鍵生成の仕組み
RSA暗号の鍵生成が、以下の手順で行われます。

  1. 素数の準備：非常に大きな、互いに異なる二つ素数p,qを用意します。
  2. 法Nの計算：これらの積N = pqを計算します。このNを「法」として使用します。
  3. オイラーのトーシェント関数：Nが持つ性質を利用するため、φ(N) = (p-1)(q-1)（オイラートーシェント関数）を計算します。これは、法Nに関する乗法群{Z_N}^*の位数(要素の個数)を表します。
  4. 公開鍵eの決定：φ(N)と互いに素である整数e (1 < e < N)を一つ選びます。(gcd(e,φ(N)) = 1)
    ※eを小さくしすぎると、脆弱になるため、通常はe = 2^{16} + 1のような値が設定されます。
  5. 秘密鍵dの計算：eとdを掛けた時にφ(N)で割ると余りが1になる整数dを計算します。(ed ≡ 1 (mod φ(N))
  6. 鍵の完成
    • 公開鍵：（N,e）
    • 秘密鍵：d

暗号化と復号

  • 暗号化
    • 送りたいメッセージ(平文)をMとし、公開鍵（N,e）を使って、暗号文cを計算します。
      c = M^e (mod N)
  • 復号
    • 暗号文cと秘密鍵dを使って、復号後のメッセージM'を計算します。
      M' = c^d (mod N)
    • この計算により、元の平文Mと復号されたM'は必ず一致します。(M = M')

素数判定法：大きな素数を探す

RSA暗号の鍵生成では、安全性を保つために非常に巨大な素数pとqを高速に見つける必要があります。このために利用されるのが素数判定法です。

Miller-Rabin素数判定法

これは、ある大きな数 n が素数であるかどうかを、完全ではないものの非常に高い確率で判定できる方法です。

  1. フェルマーの小定理の応用

    • この判定法は、「もしnが素数で、aとnが互いに素ならば、a^{n-1} \equiv 1 \pmod{n}が成り立つ」というフェルマーの小定理を利用しています。
    • この定理の対偶を取り、「もし a^{n-1} \not\equiv 1 \pmod{n} ならば、n は合成数である」という判定を行います。しかし、この条件を満たす合成数（カーマイケル数など） が存在するため、さらに改良したのがMiller-Rabin素数判定法です。

  2. 判定のステップ

    • まず、n-1 を n-1 = 2^s \cdot d （d は奇数）の形に分解します。
    • 次に、n で割り切れない任意の整数 a を選び、以下のどちらかの条件が成り立つかをテストします。
      • a^d \equiv 1 \pmod{n} が成り立つ。
      • a^d, a^{2d}, a^{4d}, \dots, a^{2^{s-1}d} のうち、どれか一つが法 n において n-1 に一致する。
    • これらのどちらかの条件を満たせば n は素数であると判定し、両方を満たさなければ n は合成数であると判定します。

RSA暗号の解読（素因数分解法）

RSA暗号の安全性を破るには、公開鍵 N=pq を元の素数 p と q に分解する（素因数分解）必要があります。これを行うための手法の一つに「p-1 法」があります。

p-1法
この方法は、合成数 N の素因子 p に対して、p-1 が「滑らか」である（p-1 が小さな素数だけで構成されている）場合に非常に有効です。

  1. 原理の利用: フェルマーの小定理より、p が素数であれば、a^{p-1} \equiv 1 \pmod{p} が成り立ちます。
  2. 因子の発見: したがって、p-1 の倍数となる数 M を考えると、a^M \equiv 1 \pmod{p}、つまり a^M - 1 は p の倍数となります。
  3. 計算: この性質を利用し、\text{gcd}(a^M - 1, N) を計算することで、高い確率で素因子 p を見つけることができます。
  4. M の選び方: p は秘密情報で不明であるため、M としては、小さな素数のべき乗を全て掛け合わせた数（「滑らかな」p-1 を約数として含む可能性が高い数）が実用的には選ばれます。

ElGamal暗号：離散対数問題の困難性を利用した公開鍵暗号

RSA暗号と並ぶ公開鍵暗号の一つにElGamal暗号があります。この暗号は、離散対数問題（DLP） という数学的な困難性を安全性の根拠としています。

  • 鍵共有の土台：Diffie-Hellman鍵共有
    ElGamal暗号の基盤を理解するために、まず二者間で安全に共通鍵を共有するための画期的な手法、Diffie-Hellman鍵共有を紹介します。

    • 仕組み
      1. 公開パラメータの準備：まず、大きな素数 p と、その p-1 を割り切る大きな素数 q を用意します。さらに、法 p に関する剰余群 \mathbb{Z}_p^* の中で、位数が q であるような特別な値 g を選びます。これらの (p, q, g) は全員に公開されます。
      2. 秘密鍵と公開鍵の生成：
        • Aliceはランダムな秘密鍵 a を選び、公開鍵 A = g^a \pmod{p} を計算します。
        • Bobもランダムな秘密鍵 b を選び、公開鍵 B = g^b \pmod{p} を計算します。
      3. 公開鍵の交換：Aliceは A をBobに、Bobは B をAliceに渡します。
      4. 共有鍵の生成：
        • Aliceは、受け取った B と自身の秘密鍵 a を使って B^a \pmod{p} を計算します。
        • Bobは、受け取った A と自身の秘密鍵 b を使って A^b \pmod{p} を計算します。
        • 結果: 両者が K = g^{ab} \pmod{p} という同じ共通鍵を導出できます。攻撃者が公開鍵 A と B を盗聴できても、秘密鍵 a や b を知らなければ、この共通鍵 K を計算することは困難とされています。

ElGamal暗号の仕組み

ElGamal暗号は、Diffie-Hellman鍵共有の概念を応用し、暗号化と復号の機能を持たせた方式です。

安全性の根拠：離散対数問題(DLP)の困難性
ElGamal暗号の安全性の核は、以下の離散対数問題（DLP: Discrete Logarithm Problem） にあります。

  • 問題：公開されている (p, q, g, y) が与えられたとき、y \equiv g^x \pmod{p} を満たす秘密の指数 x を求めよ。
    この指数 x を求めることが非常に難しいため、暗号の安全性が保たれます。

鍵生成

  1. 準備：Diffie-Hellman鍵共有と同様に、公開パラメータ (p, q, g) を決定します。
  2. 鍵の生成：
    • 秘密鍵 x：\mathbb{Z}_q からランダムに選びます。
    • 公開鍵 y：y = g^x \pmod{p} を計算します。
    • 公開鍵は (p, q, g, y)、秘密鍵は x となります。

暗号化
平文 m を暗号化するために、送信者は乱数 r を選び、暗号文 c = (c_1, c_2) を計算します。

  1. c_1 = g^r \pmod{p}
  2. c_2 = m \cdot y^r \pmod{p}

復号
暗号文 c = (c_1, c_2) と秘密鍵 x を使って、平文 m を復元します。

m = c_2 / c_1^x \pmod{p}

【復号が成り立つ理由】c_2 / c_1^x = (m \cdot y^r) / (g^r)^x = m \cdot (g^x)^r / (g^r)^x = m \cdot g^{xr} / g^{xr} = m

群の構造を利用した構成

元のElGamal暗号は、大きな素数 p を法とする剰余群 \mathbb{Z}_p^* の部分群を利用して構成されているとみなせます。

ElGamal暗号はこの位数 q の巡回部分群の上で演算を行うことで、効率的かつ安全な暗号化を実現しています。

一般の群への拡張
Elgamal暗号は、整数剰余群に限らず、一般の素数位数qと持つ可換群G に拡張できます。

鍵生成

  1. 準備：素数位数 q を持つ可換群 G と、その位数 q の生成元 g を設定します。
  2. 鍵の生成：
    秘密鍵 x：\mathbb{Z}_q からランダムに選びます。
    公開鍵 y：群 G の演算を用いて y = g^x を計算します。
    鍵の完成: 公開鍵は (G, q, g, y)、秘密鍵は x となります。

暗号化
平文 m （m \in G）に対して、送信者は乱数 r \in \mathbb{Z}_q を選び、以下の暗号文 c = (c_1, c_2) を群 G 上で計算します。

  1. c_1 = g^r
  2. c_2 = m \cdot y^r

復号
受信者は、暗号文 c = (c_1, c_2) と秘密鍵 x を使って、平文 m を復元します。

m = c_2 / c_1^x

安全性を保証する困難な問題

  1. 計算Diffie-Hellman問題 (CDH)
    Diffie-Hellman鍵共有の安全性の核心です。公開鍵 g^x と g^y（秘密の指数 x, y は不明）だけが与えられたとき、共通鍵 g^{xy} を計算上求めることが困難である、という問題です。

  2. 判定Diffie-Hellman問題 (DDH)
    g^x, g^y, g^{xy} の組と、ランダムな g^z を含む組が与えられたとき、どちらが正当な共有鍵 g^{xy} の組であるかを区別する問題です。

ElGamal暗号とCDH問題の関係
ElGamal暗号の解読の困難性は、計算Diffie-Hellman問題（CDH）の困難性と等価であるとされています。そして、離散対数問題（DLP）が解ければ、CDH問題も解けることが分かっています。

したがって、DLPを解くことが困難であるという前提が、ElGamal暗号の安全性を担保しているのです。

楕円曲線暗号(ECC)：楕円曲線離散対数問題の困難性を利用した公開鍵暗号方式

楕円曲線暗号(Elliptic Curve Cryptography)は、従来のRSA暗号やElGamal暗号よりも短い鍵長で同等以上の安全性を確保できる、極めて効率的な公開鍵暗号方式です。

安全性の根拠
楕円曲線暗号の安全性は、楕円曲線離散対数問題（ECDLP: Elliptic Curve Discrete Logarithm Problem） を解くことが非常に難しいという数学的な困難性に基づいています。

楕円曲線

暗号で使われる楕円曲線は、次のような特殊な方程式で表される、滑らかな曲線です。

E : y^2 = x^3 + ax + b (mod p)

  • p：3より大きい素数（演算の「法」）
  • a,b \in F_p（すなわち、a,bは「0, 1, 2, …, p−1」のいずれかの値）
  • 条件：4a^3 + 27b^2 \not{\equiv}0 (mod p)
    =>これにより、曲線は「特異点のない滑らかな曲線」となります。

楕円曲線上の有理点(群の要素)

この方程式を満たす有限体 \mathbb{F}_p 上の点 (x, y) を、楕円曲線上の有理点と呼びます。

\text{E}(\mathbb{F}_p) = \{(x, y) \in \mathbb{F}_p^2 \mid y^2 = x^3 + ax + b \pmod{p}\} \cup \{\mathcal{O}\}

  • \mathcal{O} は「無限遠点」と呼ばれ、これを含めた \text{E}(\mathbb{F}_p) 全体が、加法演算によって「可換群」を構成します。
  • \mathcal{O} はこの群における単位元（加法の 0 のようなもの）の役割を果たします。
  • 点 P=(x, y) の逆元は -P = (x, -y) です。

群 \text{E}(\mathbb{F}_p) における点の加法は幾何学的に定義され、点 P を n 回足し合わせる演算を n倍点[\boldsymbol{n}]\boldsymbol{P} と表記します。曲線上の点の総数を位数 \#\text{E}(\mathbb{F}_p) と呼びます。

楕円曲線離散対数問題(ECDLP)

この群の構造において、暗号の安全性の基盤となるのが ECDLP です。

  • 問題: 楕円曲線 \text{E} とその上の二点 S と T が与えられたとき、T = [d]S を満たす整数 d（スカラー）を求めよ。

つまり、点 S を何倍すれば点 T になるか、という問題です。この「何倍か」を表す秘密の指数 d を求めることが、極めて困難であるとされています。

楕円曲線暗号方式の応用

公開パラメータとして、位数が巨大な素数 r である巡回群 \text{E}(\mathbb{F}_p) と、その生成元 S が共有されていると仮定し、主要な暗号方式を紹介します。

  1. 楕円曲線上のDiffie-Hellman鍵共有(EDCH)

通常のDiffie–Hellman鍵共有(DH)を楕円曲線上の可換群に拡張したものです。

  1. 鍵の交換：参加者 A は秘密値 a から公開点 \boldsymbol{A} = [a]S を、参加者 B は秘密値 b から公開点 \boldsymbol{B} = [b]S をそれぞれ計算し、交換します。
  2. 共通鍵の計算：双方が、受け取った公開点と自身の秘密値を使って、共通鍵 \boldsymbol{K} を計算します。
    \boldsymbol{K} = [a]\boldsymbol{B} = [a][b]S = [ab]S = [b]\boldsymbol{A}

ECDHの安全性は、攻撃者が公開されている S, [a]S, [b]S から秘密値 a または b を求めるには ECDLP を解く必要があり、それが困難であることに基づきます。

  1. 楕円曲線上のElGamal暗号

DLPよりもECDLPの方が解くことが困難とされているため、ECCでは短い鍵長で高い安全性を確保でき、処理が高速になります。

  • 鍵生成：Bobが秘密鍵 \beta（乱数）を選び、公開鍵 \boldsymbol{T} = [\beta]S を計算します。
  • 暗号化：Aliceは平文を曲線上の点 M として表現し、乱数 \alpha を用いて暗号文 \boldsymbol{c} = (\boldsymbol{C}_1, \boldsymbol{C}_2) を計算します。
    • \boldsymbol{C}_1 = [\alpha]S
    • \boldsymbol{C}_2 = M + [\alpha]\boldsymbol{T}
  • 復号：Bobは暗号文 \boldsymbol{c} と秘密鍵 \beta を使って、以下の計算で平文 M を復元します。
    \boldsymbol{C}_2 - [\beta]\boldsymbol{C}_1 = (M + [\alpha]\boldsymbol{T}) - [\beta][\alpha]S = M + [\alpha][\beta]S - [\alpha][\beta]S = M
  1. 楕円曲線を利用したデジタル署名アルゴリズム(ECDSA署名)

  • 鍵生成：Aliceが秘密鍵 \alpha を選び、公開鍵 \boldsymbol{T} = [\alpha]S を計算します。

  • 署名：Aliceは乱数 k を使って点 \boldsymbol{R} = [k]S = (x, y) を計算し、平文 M と秘密鍵 \alpha を用いて署名 s \equiv k^{-1}(M + \alpha x) \pmod{r} を生成します。署名 (\boldsymbol{R}, s) を送ります。

  • 検証：Bobは \boldsymbol{R}, s と公開鍵 \boldsymbol{T} を使って検証点 \boldsymbol{V} を計算します。

    \boldsymbol{V} = [u_1]S + [u_2]\boldsymbol{T} \quad \text{ただし、} u_1 \equiv s^{-1}M \pmod{r}, u_2 \equiv s^{-1}x \pmod{r}

    \boldsymbol{V} と \boldsymbol{R} が一致する場合（\boldsymbol{V} = \boldsymbol{R}）、署名が正当であると判断します。

楕円曲線離散対数問題の解読(ρ法)

ECDLPに対する有効な解読手法の一つに、Pohlig-Hellman（ポーリグ–ヘルマン）の\rho法があります。この手法は並列処理が容易であり、特に位数が巨大な素数 r である群の解読に有効です。

\rho法の計算手順

  1. 反復関数の設定：巡回群 \langle S \rangle 上の写像 f: \langle S \rangle \to \langle S \rangle（群の中の点を同じ群の中の別の点に写す関数）を、\boldsymbol{f}(\boldsymbol{X}) = \boldsymbol{X} + [a]S + [b]T を満たすように定義します。この a, b の組は効率的に計算できる必要があります。

  2. 点の生成：

    • 初期点 \boldsymbol{X}_0 = [u_0]S + [v_0]T をランダムな整数 u_0, v_0 から生成します。
    • 反復関数 f を用いて、\boldsymbol{X}_{i+1} = f(\boldsymbol{X}_i) により、点の列 \boldsymbol{X}_i を生成します。
    • このとき、各 \boldsymbol{X}_i は \boldsymbol{X}_i = [u_i]S + [v_i]T の形で表され、整数ペア (u_i, v_i) も効率的に得られます。

  3. 衝突の検出: 巡回群 \langle S \rangle は有限集合であるため、点の列 \boldsymbol{X}_i はやがて同じ点に衝突します（\boldsymbol{X}_i = \boldsymbol{X}_j かつ i \neq j）。

  4. 解の導出: 衝突した点から、以下の関係式が得られます。

    [u_i]S + [v_i]T = [u_j]S + [v_j]T

    T=[d]S であるため、
    [u_i]S + [v_i][d]S = [u_j]S + [v_j][d]S

    ([v_i] - [v_j])[d]S = ([u_j] - [u_i])S

    もし v_i \not\equiv v_j \pmod{r} であれば、この関係式から ECDLP の解 d を導くことができます。
    d \equiv (u_i - u_j) \cdot (v_i - v_j)^{-1} \pmod{r}

暗号を支える数学的性質：群・環・体

暗号技術の安全性を理解するには、「群（Group）」「環（Ring）」「体（Field）」といった抽象的な代数構造の理解が不可欠です。これらは、特定のルールで数を操作する「数の世界」を定義します。

  1. 群(Group)

群は、最も基本的な代数構造であり、「一つの操作」に関して閉じている集合です。
集合 G とその上の二項演算 \circ が以下の 3つの性質 を満たすとき、 G は \circ に関して群であるといいます。

  1. 結合法則: どの要素 a, b, c \in G についても、(a \circ b) \circ c = a \circ (b \circ c) が成り立つ。
  2. 単位元 e の存在: どの要素 a \in G も操作しても変わらない特別な要素 e が存在する (a \circ e = e \circ a = a)。
  3. 逆元 a^{-1} の存在: どの要素 a \in G に対しても、単位元に戻す要素 a^{-1} が存在する (a \circ a^{-1} = a^{-1} \circ a = e)。
  • 可換群（アーベル群）: 上記に加えて、どの a, b \in G に対しても a \circ b = b \circ a（交換法則）が成り立つ群を指します。
  1. 環(Ring)

環は、「足し算」と「かけ算」の二つの操作に関して閉じている集合です。
集合 R 上に加法 (+) と乗法 (\cdot) の二項演算が定義され、以下の性質を満たすとき R は環であるといいます。

  1. 加法に関してアーベル群である（単位元を 0、逆元を -a と定義）。
  2. 乗法は結合法則を満たす。
  3. 乗法の単位元（1）が存在し、加法の単位元（0）とは異なる。
  4. 分配法則が成り立つ（a(b+c) = ab + ac）。
  • 可換環: 上記に加えて、乗法に関して交換法則（ab = ba）が成り立つ環を指します。
  1. 体(Field)

体は、環の性質に加え、割り算（乗法の逆元）も自由にできる、最も完全な数の世界です。
環 F が可換環であり、かつ** 0 以外のすべての要素が乗法に関する逆元を持つ**とき、 F は体であるといいます。

剰余演算と暗号への応用

暗号で頻繁に登場するのは、これらの構造を有限の数の集合に適用した「剰余系」の世界です。

  1. 剰余環 \mathbb{Z}_N と可逆元
    剰余環 \mathbb{Z}_N は、\mathbb{Z}_N = \{0, 1, 2, \dots, N-1\} という有限集合に、「法 N による加算と乗算」を定義した環です。

    • 可逆元（割り算ができる数）
      \mathbb{Z}_N の中で、乗法に対する逆元（割り算のようなもの）が存在する要素を可逆元と呼びます。
      \mathbb{Z}_N^* = \{a \in \mathbb{Z}_N \mid a \text{は乗法の逆元を持つ}\}
      • 可逆になる条件: 要素 a が逆元を持つための条件は、\text{gcd}(a, N) = 1、すなわち 「N と互いに素」 であることです。
    • 乗法群 \mathbb{Z}_N^*
      この可逆元だけを集めた集合\mathbb{Z}_N^* は、乗法に関して群をなすため、「乗法群」または「単元群」と呼ばれます。

  2. 有限体 \mathbb{F}_q

    有限体 \mathbb{F}_q は、要素の数（位数）が有限である体です。
    有限体 \mathbb{F}_q が存在するのは、その位数 q が素数 p、または素数 p のべき乗 p^k の場合に限られます。

    • 位数 q が素数 p の場合
      暗号で最も一般的に利用されるのは、位数が素数 p である有限体 \mathbb{F}_p です。
      \mathbb{F}_p = \{0, 1, 2, \dots, p-1\}

      この集合に、加法と乗法を「法 p での剰余演算（\pmod{p}）」として定義した世界のことです。
      • 性質: \mathbb{F}_p の 0 以外のすべての要素は、 p と互いに素であるため乗法の逆元を持ちます。つまり、この集合内では 0 以外のすべての数で割り算が可能です。

その他の重要な概念

  1. 位数 (Order)
  • 群の位数: その群に含まれる要素の総数です（∣G∣ などで表す）。
  • 元の位数: 群 G の元 g に対してgを何回操作（掛ける、足すなど）すれば単位元に戻るかを示す、最小の正の整数 n です。
    • 乗法表記の場合: g^n=e
    • 加法表記（楕円曲線など）の場合: nS = \mathcal{O}
  1. 巡回群 ⟨g⟩
    群Gのすべての元が、ある一つの要素gを繰り返し操作（べき乗や倍算）することで生成されるとき、 G を巡回群と呼びます。
    \text{G} = \langle g \rangle = \{e, g, g^2, \dots, g^{n-1}\}
  • 性質： 巡回群は必ず可換群であり、巡回群の位数と、その生成元 g の位数は一致します。また、位数が素数である群は必ず巡回群になります。
特徴 乗法表記（RSA, ElGamal など） 加法表記（楕円曲線暗号など）
群の演算 掛け算： ( g^a \cdot g^b = g^{a+b} ) 加算： ( aS + bS = (a+b)S )
単位元 ( e )（掛け算の単位元、1のようなもの） ( O )（無限遠点、加算の単位元）
元の表現 ( { e, g, g^2, \dots, g^{n-1} } ) ( { O, S, 2S, \dots, (r-1)S } )
元の位数 最小の ( n ) で ( g^n = e ) 最小の ( r ) で ( rS = O )
  1. オイラーのトーシェント関数
    \phi(N)この関数は、**\mathbb{Z}_N の乗法群 \mathbb{Z}_N^* の位数（要素数）**を与える非常に重要な関数です。
    \phi(N) = \lvert \{a \in \{1, 2, \dots, N-1\} \mid \text{gcd}(a, N) = 1\} \rvert
    • 意味: 1 から N-1 のうち、N と互いに素な数の個数（つまり、\mathbb{Z}_N において逆元を持つ要素の数）を数えます。

RSA暗号における応用

N が二つの素数 p と q の積（N=pq）の場合、以下の性質が成り立ちます。

\phi(N) = \phi(pq) = \phi(p) \cdot \phi(q) = (p-1)(q-1)

  1. フェルマーの小定理
    素数 n と、 n と互いに素な整数 a に対して、以下の合同式が成立するという定理です。
    a^{n-1} \equiv 1 \pmod{n}

    これは、RSA暗号の鍵生成や、素数判定法（Miller-Rabin法など）の理論的な基礎となっています。

Discussion