Python
math
数学
代数学
Python3.5

Pythonに型付けして代数拡大を実装する (2) 〜体・有理数体・ユークリッド環・剰余類環・有限体〜

More than 1 year has passed since last update.

前回は,モノイド,群,環の抽象基底クラスを作ってから整数環を実装しました。
今回は体の抽象基底クラスを作ってから,有理数体,剰余類環,有限体を実装します。

目次

  1. モノイド・群・環・整数環
  2. 体・有理数体・ユークリッド環・剰余類環・有限体
  3. 多項式環・多項式の剰余環・体の拡大

実装

体は以下のような条件に当てはまる集合です

  1. 乗法 $\star$ と加法 $\oplus$ について環である
  2. 加法単位元 $0$ を除く集合が乗法 $\star$ について群をなす

これをよく知ってる言葉に置き換えると,

  1. $1$ と $0$ が存在し,加算・減算・乗算の3つの演算ができる
  2. $0$ 以外の元が乗法逆元をもつ,すなわち $0$ 以外で割り算ができる

すなわち,四則演算(加減乗除)ができる集合となります。

クラスを実装する際は今まで作った群と環を継承し,逆元のテストをする際だけ $0$ であれば True を返すようにしておきます。

FieldType = TypeVar("FieldType", bound="Field")

class Field(Group, Ring):
    def testInverse(self: FieldType) -> bool:
        if self * self.identity() == super().zero():
            return True
        else:
            return super().testInverse()

有理数体

では,有理数体を作ります。有理数は2つの整数 $p$ と $q$ を用いて $\frac{p}{q}$ の形で表現できる数のことです。このため,有理数体クラスのインスタンスでは,常にこの $p$ と $q$ を保持しておきます。

分数が等しいことを調べる際に,単純に $p$ 同士と $q$ 同士を比較すると問題が生じます。同じ分数であっても,インスタンスによって分母が異なる場合があるからです。
この対処方法として以下の2つが考えられます。

  • $\frac{p}{q} = \frac{r}{s} \longleftrightarrow ps = qr$ を利用する
  • 両者を約分してから比較する

後で実装するユークリッドの互除法を使えば約分できますが,ここでは実装の簡単な $ps = qr$ を評価する方法をとることにします。基本的に小中学校で習ったとおりの分数の計算なので,特に説明する必要はないでしょう。

class Rational(Field):
    def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
        self.p = p
        self.q = q

    def __repr__(self: "Rational") -> str:
        if self.q == self.q.identity():
            return "%s" % self.p
        return "%s/%s" % (self.p, self.q)

    def __mul__(self: "Rational", x: "Rational") -> "Rational":
        return Rational(self.p * x.p, self.q * x.q)

    def __add__(self: "Rational", x: "Rational") -> "Rational":
        return Rational(self.p * x.q + x.p * self.q, self.q * x.q)

    def __eq__(self, x):
        if not isinstance(x, Rational):
            return NotImplemented
        return self.p * x.q == x.p * self.q

    def __neg__(self: "Rational") -> "Rational":
        return Rational(-self.p, self.q)

    def identity(self: "Rational") -> "Rational":
        return Rational(self.p.identity(), self.p.identity())

    def inverse(self: "Rational") -> "Rational":
        return Rational(self.q, self.p)

    def zero(self: "Rational") -> "Rational":
        return Rational(self.p.zero(), self.p.identity())

Q = Rational

Rational の別名は Q としておきます。

では,有理数体の動作確認をしてみましょう。

a = Q(Z( 8), Z(3))
b = Q(Z(-5), Z(4))
c = Q(Z( 3), Z(7))
y = a * b + c
print(y)
# -> -244/84

print(y.inverse())
# -> 84/-244

動きました。

現時点では約分が実装されていませんが,あとで説明するユークリッドの互除法を使えば表示の際に約分できます。

Pythonにおける有理数(分数)の実際

Pythonには分数を表現するためのクラス fractions.Fraction があります。単純に分数を扱いたいだけであれば,こちらのクラスを利用すれば十分でしょう。

from fractions import Fraction

a = 0
for i in range(10):
    a += 1/10
print(a == 1)
# -> False

a = 0
for i in range(10):
    a += Fraction(1, 10)
print(a == 1)
# -> True

Fraction を使ったソフトの例として,動画変換ソフト FFMPEG の Python インターフェイス,PyAV があります。フレームレートの計算で分数を利用しています。

ユークリッド環

これから,切り捨て除算と剰余を求める機会が増えてきます。そこで,「切り捨て除算と剰余を求めることが可能な環」としてユークリッド環の抽象基底クラスを作っておくと便利でしょう。

EuclidianRingType = TypeVar("EuclidianRingType", bound="EuclidianRing")

class EuclidianRing(Ring, metaclass=ABCMeta):
    @abstractmethod
    def __floordiv__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
        pass

    @abstractmethod
    def __mod__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
        pass

そして,Integer の親クラスを Ring から EuclidianRing に置き換え,切り捨て除算と剰余を定義します。

class Integer(EuclidianRing):

    # ~~ snip ~~

    def __floordiv__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v // x.v)

    def __mod__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v % x.v)

剰余類環

整数 $a$,$b$ と自然数 $n$ について,$a - b = n \mathbb{Z}$($\mathbb{Z}$ は任意の整数)が成り立つとき,「 $a$ と $b$ は $n$ を法として合同である」といい $a \equiv b \pmod n$ と書きます。また,このような2つの数を同じものとして扱う集合を,「 $n$ を法とする剰余類環」といいます。

では,剰余類環クラス ModRing を実装してみましょう。

剰余類環クラスのインスタンスでは,$a$ と法 $n$ を保持します。$a$ と $n$ は整数だけではなく,任意のユークリッド環を受け入れるようにします。また,画面表示する際に $a$ を0以上の最も小さい合同な数にしたいので,インスタンス作成時に $a \bmod n$ を計算しておくことにします。

次に,法の異なる数同士の計算をできないようにする必要があります。このため,ModRing はすべての剰余類環の基底クラスにすることとし,異なる法ごとにサブクラスを作るようにします。これにより,法の異なる数同士を計算しようとすると,型検査でエラーにすることができます。さらに __init__@abstractmethod にして ModRing そのものをインスタンス化できないようにしておきます。

ModRingType = TypeVar("ModRingType", bound="ModRing")
ModRingBaseType = TypeVar("ModRingBaseType", bound="EuclidianRing")

class ModRing(Ring, metaclass=ABCMeta):
    @abstractmethod
    def __init__(self: ModRingType, a: ModRingBaseType, n: ModRingBaseType) -> None:
        self.a = a % n
        self.n = n

    def __repr__(self: ModRingType) -> str:
        return "%s (mod %s)" % (str(self.a), str(self.n))

    def __mul__(self: ModRingType, x: ModRingType) -> ModRingType:
        return self.__class__(self.a * x.a)

    def __add__(self: ModRingType, x: ModRingType) -> ModRingType:
        return self.__class__(self.a + x.a)

    def __neg__(self: ModRingType) -> ModRingType:
        return self.__class__(-self.a)

    def __eq__(self, x):
        if not isinstance(x, self.__class__):
            return NotImplemented
        return self.a == x.a

    def identity(self: ModRingType) -> ModRingType:
        return self.__class__(self.a.identity())

    def zero(self: ModRingType) -> ModRingType:
        return self.__class__(self.a.zero())

各メソッドで self.__class__ とすることで,剰余類環クラスそのものではなく,除数が定められた子クラスのインスタンスを参照できます。

例えば除数5の剰余類環クラスを作る際は次のようにします。

class ModRing_5(ModRing):
    def __init__(self, a: Integer) -> None:
        super().__init__(a, Integer(5))

では,剰余類環の動作確認をしてみましょう。

まずは法の異なる数同士の計算です。

mr_3_5 = ModRing_5(Z(3))
mr_2_4 = ModRing_4(Z(2))
print(mr_3_5 + mr_2_4)
$ mypy ./field_extension.py
field_extension.py:238: error: Unsupported operand types for + ("ModRing_5" and "ModRing_4")

mypy でエラーになりました。法が同じであればエラーも出ず,問題なく計算できます。

mr_3_5 = ModRing_5(Z(3))
mr_4_5 = ModRing_5(Z(4))
print(mr_3_5 + mr_4_5) # -> 2 (mod 5)

剰余類環が体である条件

環のうち,$0$ 以外の元が乗法逆元をもつ,すなわち次の条件に当てはまるものを体と言いました。

$x \star x^{-1} = x^{-1} \star x = e$ となる $x^{-1}$ が存在

剰余類環に当てはめると,$a \pmod n$ に対して,次式を満たす整数 $p$ を見つけることが,逆元を見つけることになります。

$$a p \equiv 1 \pmod n$$

上で述べた合同の定義から,整数 $q$ を用いて

$$a p - n q = 1$$

$a$ の倍数と $n$ の倍数の和(差)は,$a$ と $n$ の最大公約数 $GCD(a, n)$ の倍数です。これをベズーの等式といいます。つまり,$GCD(a, n) = 1$ (互いに素)となります。

$n$ 未満の任意の $a$ と互いに素な $n$ は素数なので,$n$ が素数なら剰余類環が体となります。有限個の元からなる体なので,これを有限体といいます。

ユークリッドの互除法

ユークリッドの互除法を用いると,ベズーの等式 $a p + b q = r = GCD(a, b)$ を満たす整数 $p$,$q$,$r$ の組を求めることができます。

ユークリッドの互除法はユークリッド環の範囲で行うことができます。このため,ユークリッド環クラスにユークリッドの互除法を実装してしまいます。

型ヒントで,関数の引数や戻り値にタプルがある場合は typing.Tuple を用い,角カッコ内で各要素の型を指定します。

from typing import Tuple

EuclidianRingType = TypeVar("EuclidianRingType", bound="EuclidianRing")

class EuclidianRing(Ring, metaclass=ABCMeta):

    # ~~ snip ~~

    def euclid_gcd(self: EuclidianRingType, b: EuclidianRingType) -> Tuple[EuclidianRingType, EuclidianRingType, EuclidianRingType]:
        a = self
        p = a.zero()
        q = a.identity()
        p_1 = a.identity()
        q_1 = a.zero()
        while True:
            c = a % b
            if c == c.zero():
                break
            p_2 = p_1
            q_2 = q_1
            p_1 = p
            q_1 = q
            p = p_2 - p_1 * (a // b)
            q = q_2 - q_1 * (a // b)
            a = b
            b = c
        return (p, q, b)

ユークリッドの互除法を実装したので,有理数体の __init__ で約分をしてしまいましょう。

class Rational(Field):
    def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
        _, _, r =  p.euclid_gcd(q)
        self.p = p // r
        self.q = q // r

有限体

では,有限体クラスを作ります。有限体クラスは ModRing を継承して inverse メソッドを定義します。有限体の $n$ は素数でなければなりませんが,素数であることを厳密に判定するのは困難なので,インスタンスを作る際には特に検査をせず,inverse の中で互いに素か否かを調べることにします。

FiniteFieldType = TypeVar("FiniteFieldType", bound="FiniteField")

class FiniteField(Field, ModRing, metaclass=ABCMeta):
    def inverse(self: FiniteFieldType) -> FiniteFieldType:
        p, q, r = self.a.euclid_gcd(self.n)
        if r == r.identity():
            return self.__class__(p)
        raise Exception("a and n are not co-prime")

ではテストしてみましょう。

class FiniteField_11(FiniteField):
    def __init__(self, a: Integer) -> None:
        super().__init__(a, Integer(11))

ff_5_11 = FiniteField_11(Z(5))
print(ff_5_11.inverse())
# -> 9 (mod 11)

$5 \times 9 = 45 \equiv 1 \pmod {11}$ なので,$5 \pmod {11}$ の乗法逆元は確かに $9 \pmod {11}$ です。

次回予告

次回は,多項式環を定義し,今回整数のみに基づいていた ModRingFiniteField クラスを多項式に適用します。そして,最後に有理数体の拡大をしていきます。