pythonのpow関数が既約剰余類群で使えすぎて驚き

はじめに

『秋葉原ロボット部 理論グループ Advent Calendar 2024』5日目の投稿です
線形代数が大好きからはじまり、下手の横好きでガロア論に手をだしてしまいました
正直、理解が進まず、四苦八苦しております
たまたま、読書会の担当になり、逃げだそうかと思っておりましたが、親切にサポートしていただき何とか事なきをえました、いい気になってコードで書いてみたら、え、pow関数いけているんぢゃないってことで記事にしました (※アドベンカレンダーの納期あわせで、かなり雑ですが、今後リファインしますので)

Pythonのpow関数

pythonの埋め込み関数powは以下の使い方をします

pow(base, power, mod)
# 例
pow(2, 3, 5)  # 2^3(2の3乗を5で割った剰余)

この関数powの使い方が、既約剰余類群での元の求め方に、ジャストミートで驚いたので、ネタにしてみました

$$
\begin{aligned}
2^3= 2 \cdot 2 \cdot 2 = 8 = 5 + 3 \equiv 3 \ (mod 7) \\
\end{aligned}
$$

これは、法を$7$として、$2^3$が $3$と合同であるという、またこのような式を合同式という（らしい）
（※らしいではなく、その通りなのだが、怖くて言い切れない）

例えば、5の既約剰余類群における

$$
\begin{aligned}
\bar{3^1} &= \bar{3} \ (mod 5)\\
\bar{3^2} = \bar{9} &\equiv \bar{4} \ (mod 5)\\
\bar{3^3} = \bar{27} &\equiv \bar{2} \ (mod 5)\\
\bar{3^4} = \bar{81} &\equiv \bar{1} \ (mod 5)\\
\end{aligned}
$$

べき乗	0	1	2	3	4	5	6	7	$\cdots$
剰余	$\bar{4}$	$\bar{4}$	$\bar{2}$	$\bar{1}$	$\bar{3}$	$\bar{4}$	$\bar{2}$	$\bar{1}$	$\cdots$

$$
\begin{aligned}
\bar{3^5} = \bar{243} &\equiv \bar{3} \ (mod 5)\\
\bar{3^6} = \bar{729} &\equiv \bar{4} \ (mod 5)\\
\bar{3^7} = \bar{2187} &\equiv \bar{2} \ (mod 5)\\
\bar{3^8} = \bar{6561} &\equiv \bar{1} \ (mod 5)\\
\end{aligned}
$$

べき乗	0	1	2	3	4	5	6	7	$\cdots$
剰余	$\bar{4}$	$\bar{4}$	$\bar{2}$	$\bar{1}$	$\bar{3}$	$\bar{4}$	$\bar{2}$	$\bar{1}$	$\cdots$

• このようは、剰余計算にpowにさせると、どうゆうわけか、ベストフィットではないですか！！！
• 背景には、このような剰余計算は科学技術的に使い場所が多くあるためだと思われます

$$
\begin{aligned}
\bar{3^1} &= \bar{3} \ (mod 5) \ \leftrightarrow \ pow(3, 1, 5)\\
\bar{3^2} = \bar{9} &\equiv \bar{4} \ (mod 5) \ \leftrightarrow \ pow(3, 2, 5) \\
\bar{3^3} = \bar{27} &\equiv \bar{2} \ (mod 5) \ \leftrightarrow \ pow(3, 3, 5) \\
\bar{3^4} = \bar{81} &\equiv \bar{1} \ (mod 5) \ \leftrightarrow \ pow(3, 4, 5) \\
\end{aligned}
$$

既約剰余類群クラスを実装してみた

powがあまりにベストフィットで、小さな素数での原子根を見つけるのは、手計算でもよいけれど、書籍の演習問題にある素数41での原子根となると、気が遠くなってしまうので、Pythonクラスを作ってみた

class CoprimeResidueGroup:
    def __init__(self, mod):
        """
        コンストラクタでmod(法)を設定
        """
        self.mod = mod  # 法
        self.generator = None  # 原始根の候補を保持する変数

    def set_generator(self, generator):
        """
        生成元の設定（原子根の候補)
        """
        self.generator = generator  # 生成元

    def __iter__(self):
        """
        イテレータとして累乗剰余を順次生成
        """
        if self.generator is None:
            raise ValueError("原始根が設定されていません")

        current_power = 1
        result = None

        while result != 1 or current_power == 1:
            # ⭐️⭐️法をmodとする生成元の冪乗の剰余⭐️⭐️
            result = pow(self.generator, current_power, self.mod)
            yield current_power, result  # 累乗指数と剰余を返す
            current_power += 1  # 次の累乗

このクラスの使い方は以下です

• 素数7の既約剰余類群で3が原子根になるか

prime = 7
group_7 = CoprimeResidueGroup(prime)
group_7.set_generator(3)
print(f"{prime} の既約剰余類群:")
for power, result in group_7:
    print(f"{group_7.generator}^{power} ≡ {result} (mod {prime})"

実行結果

7 の既約剰余類群:
3^1 ≡ 3 (mod 7)
3^2 ≡ 2 (mod 7)
3^3 ≡ 6 (mod 7)
3^4 ≡ 4 (mod 7)
3^5 ≡ 5 (mod 7)
3^6 ≡ 1 (mod 7)

• 素数7の既約剰余類群で5が原子根になるか

group_7.set_generator(5)
print(f"{prime} の既約剰余類群:")
for power, result in group_7:
    print(f"{group_7.generator}^{power} ≡ {result} (mod {prime})")

結果

7 の既約剰余類群:
5^1 ≡ 5 (mod 7)
5^2 ≡ 4 (mod 7)
5^3 ≡ 6 (mod 7)
5^4 ≡ 2 (mod 7)
5^5 ≡ 3 (mod 7)
5^6 ≡ 1 (mod 7)

素数41の既約剰余類群

実は、原子根をたくさん持ちますが、7の場合について

prime = 41
group_41 = CoprimeResidueGroup(prime)
group_41.set_generator(7)
print(f"{prime} の既約剰余類群:")
for power, result in group_41:
    print(f"{group_41.generator}^{power} ≡ {result} (mod {prime})")

• 実行結果

41 の既約剰余類群:
7^1 ≡ 7 (mod 41)
7^2 ≡ 8 (mod 41)
7^3 ≡ 15 (mod 41)
7^4 ≡ 23 (mod 41)
7^5 ≡ 38 (mod 41)
7^6 ≡ 20 (mod 41)
7^7 ≡ 17 (mod 41)
7^8 ≡ 37 (mod 41)
7^9 ≡ 13 (mod 41)
7^10 ≡ 9 (mod 41)
7^11 ≡ 22 (mod 41)
7^12 ≡ 31 (mod 41)
7^13 ≡ 12 (mod 41)
7^14 ≡ 2 (mod 41)
7^15 ≡ 14 (mod 41)
7^16 ≡ 16 (mod 41)
7^17 ≡ 30 (mod 41)
7^18 ≡ 5 (mod 41)
7^19 ≡ 35 (mod 41)
7^20 ≡ 40 (mod 41)
7^21 ≡ 34 (mod 41)
7^22 ≡ 33 (mod 41)
7^23 ≡ 26 (mod 41)
7^24 ≡ 18 (mod 41)
7^25 ≡ 3 (mod 41)
7^26 ≡ 21 (mod 41)
7^27 ≡ 24 (mod 41)
7^28 ≡ 4 (mod 41)
7^29 ≡ 28 (mod 41)
7^30 ≡ 32 (mod 41)
7^31 ≡ 19 (mod 41)
7^32 ≡ 10 (mod 41)
7^33 ≡ 29 (mod 41)
7^34 ≡ 39 (mod 41)
7^35 ≡ 27 (mod 41)
7^36 ≡ 25 (mod 41)
7^37 ≡ 11 (mod 41)
7^38 ≡ 36 (mod 41)
7^39 ≡ 6 (mod 41)
7^40 ≡ 1 (mod 41)

後記

時間もなく、内容も不十分ですが、なんだかおもしろいかもって思えてきました、（自分のことですが）
修正の指摘やコメントなどよろしくお願いいたします