拡張されたユークリッドの互除法 (実装)

• #1 : ユークリッドの互除法
• #2 : 拡張されたユークリッドの互除法 (導入)
• #3 : 拡張されたユークリッドの互除法 (実装)

概要

ユークリッドの互除法によって、2 つの整数 $a, b$ の最大公約数を求めつつ、一次不定方程式 $ax + by = {\rm gcd}(a, b)$ の解 $(x, y)$ を求める実装を Python で行います。

今回は、行列演算を用いて 1 回のループで計算を済ませたいと思います。

最終的な実装は、以下の通りです。

from typing import Tuple

# 再帰的に簡潔に記述するパターン
def ex_gcd(
    a: int,
    b: int,
    x: int = 1,
    y: int = 0,
    u: int = 0,
    v: int = 1,
) -> Tuple[int, int, int]:
    return (a, x, y) if b == 0 else ex_gcd(
        b,
        a % b,
        u,
        v,
        x - (a // b) * u,
        y - (a // b) * v,
    )

print(ex_gcd(8767, 4664))
# (11, 133, -250)

# 計算内容を意識して再帰的に記述しないパターン
def extended_euclidean_algorithm(a: int, b: int) -> Tuple[int, int, int]:

    x: int = 1
    y: int = 0
    u: int = 0
    v: int = 1

    while b != 0:
        x, u = u, x - (a // b) * u
        y, v = v, y - (a // b) * v
        a, b = b, a % b

    return a, x, y

print(extended_euclidean_algorithm(8767, 4664))
# (11, 133, -250)

連立方程式は行列を使って解く

前回 のユークリッドの互除法の除算を再掲します。

任意の正整数 $a, b$ に対して、$r_0 = a, \ r_1 = b, \ r_n = {\rm gcd}(a, b)$ とすると、以下の通りになりました。

$$ \begin{align} r_0 &= q_0 r_1 + r_2 \\ r_1 &= q_1 r_2 + r_3 \\ r_2 &= q_2 r_3 + r_4 \\ \vdots \\ r_{n-3} &= q_{n-3} r_{n-2} + r_{n-1} \\ r_{n-2} &= q_{n-2} r_{n-1} + r_n \\ r_{n-1} &= q_{n-1} r_n \end{align} $$

この後、下から順に移項と代入を繰り返していくわけですが、これは $r_i \ (0 \leq i \leq n)$ を未知数とする連立方程式を解くことに他なりません。

したがって、まずはこの連立方程式を行列で書き直してみます。

$$ \begin{align} \left( \begin{array}{c} r_0 \\ r_1 \end{array} \right) &= \left( \begin{array}{cc} q_0 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} r_1 \\ r_2 \end{array} \right) \\ \left( \begin{array}{c} r_1 \\ r_2 \end{array} \right) &= \left( \begin{array}{cc} q_1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} r_2 \\ r_3 \end{array} \right) \\ \left( \begin{array}{c} r_2 \\ r_3 \end{array} \right) &= \left( \begin{array}{cc} q_2 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} r_3 \\ r_4 \end{array} \right) \\ \vdots \\ \left( \begin{array}{c} r_{n-3} \\ r_{n-2} \end{array} \right) &= \left( \begin{array}{cc} q_{n-3} & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} r_{n-2} \\ r_{n-1} \end{array} \right) \\ \left( \begin{array}{c} r_{n-2} \\ r_{n-1} \end{array} \right) &= \left( \begin{array}{cc} q_{n-2} & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} r_{n-1} \\ r_n \end{array} \right) \\ \left( \begin{array}{c} r_{n-1} \\ r_n \end{array} \right) &= \left( \begin{array}{cc} q_{n-1} & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} r_n \\ 0 \end{array} \right) \end{align} $$

これをまとめると、以下のような式に変形できました。

$$ \left( \begin{array}{c} a \\ b \end{array} \right) = \left( \begin{array}{cc} q_0 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} q_1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} q_2 & 1 \\ 1 & 0 \end{array} \right) \cdots \left( \begin{array}{cc} q_{n-3} & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} q_{n-2} & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} q_{n-1} & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} {\rm gcd}(a, b) \\ 0 \end{array} \right) $$

なお、$r_0 = a, \ r_1 = b, \ r_n = {\rm gcd}(a, b)$ は元に戻しています。

両辺の左から逆行列を掛けていく

$Q_i = \left( \begin{array}{cc} q_i & 1 \\ 1 & 0 \end{array} \right) \ (0 \leq i \leq n-1)$ とおくと、以下のように書き直せます。

$$ \left( \begin{array}{c} a \\ b \end{array} \right) = Q_0 Q_1 Q_2 \cdots Q_{n-3} Q_{n-2} Q_{n-1} \left( \begin{array}{c} {\rm gcd}(a, b) \\ 0 \end{array} \right) $$

ここで、行列式 ${\rm det} \ Q_i = -1 \neq 0$ より、行列 $Q_i$ は正則行列であり、逆行列が存在することが分かります。

したがって、逆行列 $Q_i^{-1} = \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_i \end{array} \right) \ (0 \leq i \leq n-1)$ を両辺の左から順番に掛けていくと、以下のようになります。

$$ Q_{n-1}^{-1} Q_{n-2}^{-1} Q_{n-3}^{-1} \cdots Q_2^{-1} Q_1^{-1} Q_0^{-1} \left( \begin{array}{c} a \\ b \end{array} \right) = \left( \begin{array}{c} {\rm gcd}(a, b) \\ 0 \end{array} \right) \\ \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_{n-1} \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_{n-2} \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_{n-3} \end{array} \right) \cdots \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_2 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_1 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_0 \end{array} \right) \left( \begin{array}{c} a \\ b \end{array} \right) = \left( \begin{array}{c} {\rm gcd}(a, b) \\ 0 \end{array} \right) $$

あとは、以下のようにおくことで、

$$ \begin{align} \left( \begin{array}{cc} x & y \\ u & v \end{array} \right) &= \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_{n-1} \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_{n-2} \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_{n-3} \end{array} \right) \cdots \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_2 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_1 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_0 \end{array} \right) \end{align} $$

最終的に、このような簡潔な形で書き表すことができました。

$$ \left( \begin{array}{cc} x & y \\ u & v \end{array} \right) \left( \begin{array}{c} a \\ b \end{array} \right) = \left( \begin{array}{c} {\rm gcd}(a, b) \\ 0 \end{array} \right) $$

この行列 $\left( \begin{array}{cc} x & y \\ u & v \end{array} \right)$ を求めることで、一次不定方程式 $ax + by = {\rm gcd}(a, b)$ の解 $(x, y)$ を求められるというわけです。

解を求めるアルゴリズム

最後に、行列 $\left( \begin{array}{cc} x & y \\ u & v \end{array} \right)$ を求めるアルゴリズムを考えるわけですが、これは単純で、$Q_0$ から順番に左から $Q_i$ を掛けていくだけです。

ユークリッドの互除法において、除算の商 $q_i$ の値が判明する順番は $q_0, q_1, q_2, \ldots$ となっているわけですから、対応する行列 $Q_i^{-1}$ の値が判明する順番は $Q_0^{-1}, Q_1^{-1}, Q_2^{-1}, \ldots$ となります。

そのため、1 回のループの中で最大公約数を求める過程と並行して、一次不定方程式の解を求められるというわけです。

アルゴリズムとしては、単位行列 $\left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)$ の左から $Q_i^{-1} = \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_i \end{array} \right) \ (0 \leq i \leq n-1)$ を掛けていくので、$x_0 = 1, \ y_0 = 0, \ u_0 = 0, \ v_0 = 1$ としたとき、以下のように順に計算していくことになります。

$$ \begin{align} \left( \begin{array}{cc} x_1 & y_1 \\ u_1 & v_1 \end{array} \right) &= \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_0 \end{array} \right) \left( \begin{array}{cc} x_0 & y_0 \\ u_0 & v_0 \end{array} \right) = \left( \begin{array}{cc} u_0 & v_0 \\ x_0 - q_0 u_0 & y_0 - q_0 v_0 \end{array} \right) \\ \left( \begin{array}{cc} x_2 & y_2 \\ u_2 & v_2 \end{array} \right) &= \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_1 \end{array} \right) \left( \begin{array}{cc} x_1 & y_1 \\ u_1 & v_1 \end{array} \right) = \left( \begin{array}{cc} u_1 & v_1 \\ x_1 - q_1 u_1 & y_1 - q_1 v_1 \end{array} \right) \\ \left( \begin{array}{cc} x_3 & y_3 \\ u_3 & v_3 \end{array} \right) &= \left( \begin{array}{cc} 0 & 1 \\ 1 & -q_2 \end{array} \right) \left( \begin{array}{cc} x_2 & y_2 \\ u_2 & v_2 \end{array} \right) = \left( \begin{array}{cc} u_2 & v_2 \\ x_2 - q_2 u_2 & y_2 - q_2 v_2 \end{array} \right) \\ \vdots \end{align} $$

これを、ユークリッドの互除法と合わせて書き下すと、以下のようになります。

1. 2 つの整数を $a, b$ とする。また、$x = 1, \ y = 0, \ u = 0, \ v = 1$ を初期値とする
2. $b = 0$ ならば、$a$ が最大公約数であり、$x, y$ が一次不定方程式の解であるため、アルゴリズムを終了する
3. $b \neq 0$ ならば、$a$ を $b$ で除算した商を $q$ 、剰余を $r$ とするとき、$b, r$ を新たな $a, b$ として、さらに $u, v, x-qu, y-qv$ を新たな $x, y, u, v$ として、手順 2 に戻る

これを Python で実装したのが冒頭のコードです。

以上で、2 つの整数 $a, b$ の最大公約数を求めつつ、一次不定方程式 $ax + by = {\rm gcd}(a, b)$ の解 $(x, y)$ を求めるアルゴリズムがすっきりする形にできたかなと思います。

メモ

これで一段落です。

すっきりした形になったと書きましたが、実際の計算量とか実行速度のことは検証していません。興味がないので検証はしません。

綺麗に書けたということに意義がある、自己満足のためのものです。

また、これを利用した RSA 暗号の話については、面倒でなければそのうち書くと思います。

拡張されたユークリッドの互除法 (導入)

• #1 : ユークリッドの互除法
• #2 : 拡張されたユークリッドの互除法 (導入)
• #3 : 拡張されたユークリッドの互除法 (実装)

概要

前回 のユークリッドの互除法により、2 つの整数の最大公約数を効率的に求めることができるようになりました。

しかし、ユークリッドの互除法によって、2 つの整数 $a, b$ の最大公約数を求めるだけでなく、一次不定方程式 $ax + by = {\rm gcd}(a, b)$ の解 $(x, y)$ を求めることができます。

どういうことかというと、例えば、前回の例でいうと $8767$ と $4664$ の最大公約数は $11$ でした。

このとき、一次不定方程式 $8767 x + 4664 y = 11$ の解 $(x, y)$ を求めることができるというわけです。ちなみに、$(x, y) = (133, -250)$ となります。

一応、Python での実装を最後のほうに載せますが、まだ愚直な実装しかしていません。本格的な実装は次回以降にしたいと思います。

具体例

前回の例をそのまま使用して、$8767$ と $4664$ のユークリッドの互除法を考えて、一次不定方程式 $8767 x + 4664 y = {\rm gcd}(8767, 4664)$ の解 $(x, y)$ を求めてみます。

一般に、$a, b$ の除算の商 $q$ と剰余 $r$ としたとき、$a = qb + r$ と表せることから、$r = a - qb$ と変形できるので、ユークリッドの互除法の除算をすべてこの形で表すことにします。

$$ \begin{align} 4103 &= 8767 - 1 \times 4664 \\ 561 &= 4664 - 1 \times 4103 \\ 176 &= 4103 - 7 \times 561 \\ 33 &= 561 - 3 \times 176 \\ 11 &= 176 - 5 \times 33 \end{align} $$

このうち、最後の式の左辺が ${\rm gcd}(8767, 4664)$ であることから、右辺を変形していって $8767 x + 4664 y$ の形を目指すと良さそうです。

最後の式の右辺の $33$ は、その一段上の式 $33 = 561 - 3 \times 176$ の左辺であるため、代入して整理することができます。

同様に、右辺の $176$ に、さらに一段上の $176 = 4103 - 7 \times 561$ が代入できるので、この代入操作を下から上へ逆順にたどっていくと、以下のようになります。

$$ \begin{align} 11 &= 176 - 5 \times 33 \\ &= 176 - 5 \times ( 561 - 3 \times 176 ) \\ &= - 5 \times 561 + 16 \times 176 \\ &= - 5 \times 561 + 16 \times ( 4103 - 7 \times 561 ) \\ &= 16 \times 4103 - 117 \times 561 \\ &= 16 \times 4103 - 117 \times ( 4664 - 1 \times 4103 ) \\ &= - 117 \times 4664 + 133 \times 4103 \\ &= - 117 \times 4664 + 133 \times ( 8767 - 1 \times 4664 ) \\ &= 133 \times 8767 - 250 \times 4664 \end{align} $$

よって、$8767 \times 133 + 4664 \times (- 250) = 11$ ということが分かったので、解を $(x, y) = (133, -250)$ と求めることができました。

一般化

具体的な計算方法が分かったので、Python での実装に向けて一般化していきたいと思います。

まずは、任意の正整数 $a, b$ に対して、以下のようにユークリッドの互除法の除算を行います。なお、$r_0 = a, \ r_1 = b, \ r_n = {\rm gcd}(a, b)$ とします。

$$ \begin{align} r_0 &= q_0 r_1 + r_2 \\ r_1 &= q_1 r_2 + r_3 \\ r_2 &= q_2 r_3 + r_4 \\ \vdots \\ r_{n-3} &= q_{n-3} r_{n-2} + r_{n-1} \\ r_{n-2} &= q_{n-2} r_{n-1} + r_n \\ r_{n-1} &= q_{n-1} r_n \end{align} $$

次に、具体例で挙げたような代入操作を、とりあえず 1 回だけ行ってみます。

$$ \begin{align} r_n &= r_{n-2} - q_{n-2} r_{n-1} \\ &= r_{n-2} - q_{n-2} ( r_{n-3} - q_{n-3} r_{n-2} ) \\ &= - q_{n-2} r_{n-3} + (1 + q_{n-2} q_{n-3}) r_{n-2} \end{align} $$

この次の代入操作を行うには、係数が煩雑であるため、$X_{n-2} = - q_{n-2}, \ Y_{n-2} = 1 + q_{n-2} q_{n-3}$ とおきます。この状態でもう 1 回操作を行います。

$$ \begin{align} r_n &= X_{n-2} r_{n-3} + Y_{n-2} r_{n-2} \\ &= X_{n-2} r_{n-3} + Y_{n-2} ( r_{n-4} - q_{n-4} r_{n-3} ) \\ &= Y_{n-2} r_{n-4} + (X_{n-2} - Y_{n-2} q_{n-4}) r_{n-3} \end{align} $$

これで、$r_{n-4}, \ r_{n-3}$ のそれぞれの係数を $X_{n-3} = Y_{n-2}, \ Y_{n-3} = X_{n-2} - Y_{n-2} q_{n-4}$ とおくことで、次からの代入操作も同じように行うことができます。

これをアルゴリズムとして考えると、以下の手順になります。

1. ユークリッドの互除法の手順における商を、順に配列で保持する
2. 最後の商は割り切ったときのものであるため、その次の商 $q_1$ から開始する
3. 初期値を $X = 1, \ Y = - q_1$ とする
4. 次の商 $q$ が存在しない場合、$X, Y$ が一次不定方程式の解であるため、アルゴリズムを終了する
5. 次の商 $q$ が存在する場合、$Y, \ X-Yq$ を新たな $X, \ Y$ として、手順 4 に戻る

まずは愚直に実装してみる

拡張されたユークリッドの互除法のアルゴリズムを考えることができたので、Python でそのまま実装してみます。

from typing import List, Tuple

def extended_euclidean_algorithm(a: int, b: int) -> Tuple[int, int, int]:

    # ユークリッドの互除法

    quotients: List[int] = []

    while b != 0:
        quotients.append(a // b)
        r: int = a % b
        a = b
        b = r

    # 一次不定方程式の解

    quotients.reverse()

    x: int = 1
    y: int = -quotients[1]

    for q in quotients[2:]:
        new_x: int = y
        new_y: int = x - y * q
        x = new_x
        y = new_y

    return a, x, y


print(extended_euclidean_algorithm(8767, 4664))
# (11, 133, -250)

これでも求める結果は得られるのですが、2 回も同じようなループするのはいささか不格好に見えます。

次回以降では、行列演算を用いて 1 回のループで計算することを目指したいと思います。

追記 (2021-09-29)

次回の 拡張されたユークリッドの互除法 (実装) を投稿しました。

ユークリッドの互除法

• #1 : ユークリッドの互除法
• #2 : 拡張されたユークリッドの互除法 (導入)
• #3 : 拡張されたユークリッドの互除法 (実装)

概要

ユークリッドの互除法 (Euclidean algorithm) とは、2 つの整数の最大公約数を効率的に求めるアルゴリズムのことです。

最古のアルゴリズムと呼ばれているらしいです。

Python で実装するならば、以下の通りです。

# 再帰的に簡潔に記述するパターン
def gcd(a: int, b: int) -> int:
    return a if b == 0 else gcd(b, a % b)

print(gcd(8767, 4664))
# 11


# アルゴリズムの手順をそのまま記述するパターン
def euclidean_algorithm(a: int, b: int) -> int:

    while b != 0:
        r: int = a % b
        a = b
        b = r

    return a

print(euclidean_algorithm(8767, 4664))
# 11

ユークリッドの互除法の手順

2 つの整数に対して、以下の手順を繰り返すことで最大公約数を求めることができます。

1. 2 つの整数を $a, b$ とする
2. $b = 0$ ならば、$a$ が最大公約数であるため、アルゴリズムを終了する
3. $b \neq 0$ ならば、$a$ を $b$ で除算した剰余を $r$ とするとき、$b, r$ を新たな 2 数として最初に戻る

例

$8767$ と $4664$ の最大公約数を、ユークリッドの互除法によって求めます。

$$ \begin{align} 8767 \div 4664 &= 1 \ \ldots \ 4103 \\ 4664 \div 4103 &= 1 \ \ldots \ 561 \\ 4103 \div 561 &= 7 \ \ldots \ 176 \\ 561 \div 176 &= 3 \ \ldots \ 33 \\ 176 \div 33 &= 5 \ \ldots \ 11 \\ 33 \div 11 &= 3 \end{align} $$

以上より、最大公約数は $11$ と求められました。

なぜ、最大公約数が得られるのか

ユークリッドの互除法の手順では、最初の 2 数 $a, b$ ではなく、その剰余 $r$ を用いて $b, r$ 、あるいはその次と、最初の 2 数ではないものを次々と計算しています。

そうであるにもかかわらず、最初の 2 数の最大公約数が求められるということは、次の命題が成立するということです。

以下、$a, b$ の最大公約数のことを記号を用いて ${\rm gcd}(a, b)$ と表します。G.C.D. とは最大公約数 (greatest common divisor) のことです。

命題

任意の正整数 $a, b$ について、$a$ を $b$ で除算した剰余を $r$ とするとき、

$$ {\rm gcd}(a, b) = {\rm gcd}(b, r) $$

が成立する。

証明

任意の正整数 $a, b$ について、$a$ を $b$ で除算した商を $q$ 、剰余を $r$ とすると、

$$ a = qb + r $$

また、${\rm gcd}(a, b) = d, \ {\rm gcd}(b, r) = d'$ と置くとき、

$$ \begin{align} ({\rm i}) \ d &\leq d' \\ ({\rm ii}) \ d &\geq d' \end{align} $$

を示すことで、$d = d'$ を示す。

$({\rm i})$ $d \leq d'$ を示す。

${\rm gcd}(a, b) = d$ より、正整数 $a', b'$ を用いて $a=a'd, \ b=b'd$ と表せる。

$a=qb+r$ より、

$$ \begin{align} r &= a - qb \\ &= a'd - q \cdot b'd \\ &= (a' - qb')d \end{align} $$

となるため、$d$ は $r$ の約数である。

一方、$d$ は ${\rm gcd}(a, b) = d$ より $b$ の約数でもあることから、$b, r$ の公約数である。

したがって、${\rm gcd}(b, r) = d'$ より、$d \leq d'$ が示された。

$({\rm ii})$ $d \geq d'$ を示す。

${\rm gcd}(b, r) = d'$ より、正整数 $b'', r''$ を用いて $b=b''d', \ r=r''d'$ と表せる。

$a=qb+r$ より、

$$ \begin{align} a &= qb + r \\ &= q \cdot b''d' + r''d' \\ &= (qb'' + r'')d' \end{align} $$

となるため、$d'$ は $a$ の約数である。

一方、$d'$ は ${\rm gcd}(b, r) = d'$ より $b$ の約数でもあることから、$a, b$ の公約数である。

したがって、${\rm gcd}(a, b) = d$ より、$d \geq d'$ が示された。

以上より、$({\rm i}) ({\rm ii})$ が示されたので、$d = d'$ が示された。

実際の値で処理を追ってみる

既に例に挙げた $8767$ と $4664$ のユークリッドの互除法による以下の処理について、その過程を命題とともに観察してみます。

$$ \begin{align} 8767 \div 4664 &= 1 \ \ldots \ 4103 \\ 4664 \div 4103 &= 1 \ \ldots \ 561 \\ 4103 \div 561 &= 7 \ \ldots \ 176 \\ 561 \div 176 &= 3 \ \ldots \ 33 \\ 176 \div 33 &= 5 \ \ldots \ 11 \\ 33 \div 11 &= 3 \end{align} $$

まず、$8767 \div 4664 = 1 \ \ldots \ 4103$ より、剰余が $4103$ なので、命題より ${\rm gcd}(8767, 4664) = {\rm gcd}(4664, 4103)$ が分かります。

次に、$4664 \div 4103 = 1 \ \ldots \ 561$ より、剰余が $561$ なので、命題より ${\rm gcd}(4664, 4103) = {\rm gcd}(4103, 561)$ が分かります。

同様の除算を繰り返して、命題より以下の通りになることが分かりました。

$$ \begin{align} {\rm gcd}(8767, 4664) &= {\rm gcd}(4664, 4103) \\ &= {\rm gcd}(4103, 561) \\ &= {\rm gcd}(561, 176) \\ &= {\rm gcd}(176, 33) \\ &= {\rm gcd}(33, 11) \\ \end{align} $$

最後の 2 数において $33 \div 11 = 3$ となり割り切れるということは、$11$ が $33$ の約数であり、かつ、$11$ が 2 数の最大公約数であるということです。

したがって、${\rm gcd}(33, 11) = 11$ となり、命題より ${\rm gcd}(8767, 4664) = 11$ と求められるわけです。

メモ

元々は、RSA 暗号を数学的に理解することを目的として、書き始めたものです。

そのため、この後に拡張されたユークリッドの互除法、RSA 暗号と続きます。

ただ、途中からは拡張されたユークリッドの互除法の Python での実装の方に熱が入り、RSA 暗号はおまけになりました。

気が向いたら、続きを書いていく予定です。

追記 (2021-09-28)

次回の 拡張されたユークリッドの互除法 (導入) を投稿しました。

Python 仮想環境 (venv)

コピペするためのメモです。

仮想環境を作成する

$ python3 -m venv venv
$ touch requirements.txt

仮想環境をアクティベートする

Mac

$ source venv/bin/activate

Windows

$ .\venv\Scripts\activate

必要なモジュールをインストールする

$ pip install -r requirements.txt

仮想環境をデアクティベートする

$ deactivate