あけおめ計算〜 (原始根をただ計算する)

導入

> 2 ** 4 % 5
1
> 3 ** 16 % 17
1
> 5 ** 96 % 97
1
> r ** (p - 1) % p
1

なんか $11$ になります！

あけおめなので、抱負

ん〜、

• おすすめされた本を読む
• 技術同人誌書く

とかですかね

原始根

いきなりですが、これは原始根です！

一般には、$pp$ を素数とすると、適当に $rr$ を取れば

$$r1≢1(mod p)r2≢1(mod p)⋯rp−2≢1(mod p)rp−1≡1(mod p)\begin{aligned} r^1 &\not\equiv 1 \quad (\mathrm{mod} \ p) \\ r^2 &\not\equiv 1 \quad (\mathrm{mod} \ p) \\ &\cdots \\ r^{p-2} &\not\equiv 1 \quad (\mathrm{mod} \ p) \\ \textcolor{red}{r^{p-1}} &\textcolor{red}{\equiv 1 \quad (\mathrm{mod} \ p)} \end{aligned}$$

$rr$ を $pp$ に対応する原始根と言います

$p=5p = 5$, $r=2r = 2$ の場合

$$21≡2(mod p)22≡4(mod p)23≡3(mod p)24≡1(mod p)\begin{aligned} 2^1 &\equiv 2 \quad (\mathrm{mod} \ p) \\ 2^2 &\equiv 4 \quad (\mathrm{mod} \ p) \\ 2^3 &\equiv 3 \quad (\mathrm{mod} \ p) \\ \textcolor{red}{2^4} &\textcolor{red}{\equiv 1 \quad (\mathrm{mod} \ p)} \end{aligned}$$

「いつ使うのか？」というと、フーリエ変換で使いますが、それはまた今度にして、今回は原始根を計算することに全集中します。素数 $pp$ を与えられたら、$rr$ を計算できるようにしたいということです！

$5757$ に対応する原始根は何かわかりますか？

ちなみに、任意の有限体でも、乗法群は巡回群になります
証明は忘れました

原始根の計算方法

方針としては、$r=1,2,3,…r = 1, 2, 3, \dots$ と順番に見ていって、それが原始根になるか試します

普通にやると $r,r2,r3,…r, r^2, r^3, \dots$ を $pp$ で割った余りを順番に計算して、$…,rp−3,rp−2\dots, r^{p - 3}, r^{p - 2}$ までずっと $≢1\not\equiv 1$ で、$rp−1r^{p - 1}$ で初めて $≡1\equiv 1$ になることをチェックすればいいです

$pp$ が大きい場合はしんどそうです、、、なので、原始根かどうかをある程度効率的に判定したいですが、次のような判定条件があります:
$p−1=q1⋯qkp - 1 = q_1 \cdots q_k$ と素因数分解したとき

$$rp−1qi≢1(mod p)(1≤i≤k)r^\frac{p - 1}{q_i} \not\equiv 1 \quad (\mathrm{mod} \ p) \qquad (1 \le i \le k)$$

が成り立てば $rr$ は $pp$ に対応する原始根になる

$p=97p = 97$ の場合
$p−1=96=25⋅3p - 1 = 96 = 2^5 \cdot 3$
$r=1r = 1$ では

$$r962=r48=1→ダメr^\frac{96}{2} = r^{48} = 1 \qquad \to \text{ダメ}$$

$r=2r = 2$ では

$$r962=r48=281474976710656≡1(mod 97)→ダメr^\frac{96}{2} = r^{48} = 281474976710656 \equiv 1 \quad (\mathrm{mod} \ 97) \qquad \to \text{ダメ}$$

$r=3r = 3$ では

$$r962=r48=79766443076872509863361≡1(mod 97)→ダメr^\frac{96}{2} = r^{48} = 79766443076872509863361 \equiv 1 \quad (\mathrm{mod} \ 97) \qquad \to \text{ダメ}$$

$r=4r = 4$ では

$$r962=r48=79228162514264337593543950336≡1(mod 97)→ダメr^\frac{96}{2} = r^{48} = 79228162514264337593543950336 \equiv 1 \quad (\mathrm{mod} \ 97) \qquad \to \text{ダメ}$$

$r=5r = 5$ では

$$r962=r48=3552713678800500929355621337890625≡96(mod 97)r963=r32=23283064365386962890625≡35(mod 97)→OK\begin{aligned} &r^\frac{96}{2} = r^{48} = 3552713678800500929355621337890625 \equiv 96 \quad (\mathrm{mod} \ 97) \\ &r^\frac{96}{3} = r^{32} = 23283064365386962890625 \equiv 35 \quad (\mathrm{mod} \ 97) \\ &\to \text{OK} \end{aligned}$$

$r=5r = 5$ は $p=97p = 97$ に対応する原始根なことがわかりました

繰り返し 2 乗法

前節で $3483^{48}$ を $9797$ で割った余りなどを計算しましたが、愚直に計算すると

$$31=3(mod 97)32=3⋅3=9(mod 97)33=9⋅3=27(mod 97)34=27⋅3=81(mod 97)35=81⋅3=243≡49(mod 97)36≡49⋅3=147≡50(mod 97)⋯⋯⋯347≡54⋅3=162≡65(mod 97)348≡65⋅3=195≡1(mod 97)\begin{aligned} 3^1 &= 3 &\quad (\mathrm{mod} \ 97) \\ 3^2 &= 3 \cdot 3 = 9 &\quad (\mathrm{mod} \ 97) \\ 3^3 &= 9 \cdot 3 = 27 &\quad (\mathrm{mod} \ 97) \\ 3^4 &= 27 \cdot 3 = 81 &\quad (\mathrm{mod} \ 97) \\ 3^5 &= 81 \cdot 3 = 243 \equiv 49 &\quad (\mathrm{mod} \ 97) \\ 3^6 &\equiv 49 \cdot 3 = 147 \equiv 50 &\quad (\mathrm{mod} \ 97) \\ &\cdots \\ &\cdots \\ &\cdots \\ 3^{47} &\equiv 54 \cdot 3 = 162 \equiv 65 &\quad (\mathrm{mod} \ 97) \\ 3^{48} &\equiv 65 \cdot 3 = 195 \equiv 1 &\quad (\mathrm{mod} \ 97) \end{aligned}$$

と計算することになります

ですが、先に $31,32,34,…3^1, 3^2, 3^4, \dots$ を計算しておきます:

$$31=3(mod 97)32=3⋅3=9(mod 97)34=9⋅9=81(mod 97)38=81⋅81=6561≡62(mod 97)316≡62⋅62=3844≡61(mod 97)332≡61⋅61=3721≡35(mod 97)\begin{aligned} 3^1 &= 3 &\quad (\mathrm{mod} \ 97) \\ 3^2 &= 3 \cdot 3 = 9 &\quad (\mathrm{mod} \ 97) \\ 3^4 &= 9 \cdot 9 = 81 &\quad (\mathrm{mod} \ 97) \\ 3^8 &= 81 \cdot 81 = 6561 \equiv 62 &\quad (\mathrm{mod} \ 97) \\ 3^{16} &\equiv 62 \cdot 62 = 3844 \equiv 61 &\quad (\mathrm{mod} \ 97) \\ 3^{32} &\equiv 61 \cdot 61 = 3721 \equiv 35 &\quad (\mathrm{mod} \ 97) \end{aligned}$$

そして $4848$ を $48=16+3248 = 16 + 32$ と $22$ 進展開すると

$$348=316+32=316⋅332≡61⋅35=2135≡1(mod 97)3^{48} = 3^{16 + 32} = 3^{16} \cdot 3^{32} \equiv 61 \cdot 35 = 2135 \equiv 1 \quad (\mathrm{mod} \ 97)$$

のように計算を減らすことができます。$pp$ が大きくなると影響は顕著です

最後に "type"script で

新年なので、typescript に計算させましょう！

型レベルで四則演算をできるライブラリを探していたら、↓を見つけました
https://github.com/gvergnaud/hotscript
使い心地はかなり良かったですが、再帰回数が多くなりがちな気もします。でも、おすすめかも

codesandbox

https://codesandbox.io/p/devbox/primitive-root-qdz2xm

コード

import type {
  _,
  Call,
  Fn,
  Numbers,
  PartialApply,
  Pipe,
  Tuples,
  Unions,
} from 'hotscript';

// 素因数分解
// N >= 1
type PrimeFactors<N extends number, Q extends number = 2> =
  Call<Numbers.LessThanOrEqual<Call<Numbers.Mul<Q, Q>>, N>> extends true
    ? Call<Numbers.Equal<Call<Numbers.Mod<N, Q>>, 0>> extends true
      ? PrimeFactors<Call<Numbers.Div<N, Q>>, Q> | Q
      : PrimeFactors<N, Call<Numbers.Add<Q, 1>>>
    : N extends 1
      ? never
      : N;

// 剰余を取りながら乗算
type PMul<A extends number, B extends number, P extends number> = Call<
  Numbers.Mod<Call<Numbers.Mul<A, B>>, P>
>;

// 繰り返し 2 乗法
// 0 <= R < P, N >= 0
// 再帰上限突破のために、5 進法を使っている
type PPow<
  R extends number,
  N extends number,
  P extends number,
  RPowMap extends Record<number, number> = {
    0: 1;
    1: R;
    2: PMul<R, R, P>;
    3: PMul<PMul<R, R, P>, R, P>;
    4: PMul<PMul<R, R, P>, PMul<R, R, P>, P>;
  },
> =
  Call<Numbers.Equal<N, 0>> extends true
    ? 1
    : PMul<
        PPow<PMul<R, RPowMap[4], P>, Call<Numbers.Div<N, 5>>, P>,
        RPowMap[Call<Numbers.Mod<N, 5>>],
        P
      >;

// hotscript 用
interface PPowFn extends Fn {
  return: PPow<this['arg0'], this['arg1'], this['arg2']>;
}

type IsPrimitiveRoot<
  P extends number,
  R extends number,
  T extends number,
> = Pipe<
  PrimeFactors<T>,
  [
    Unions.ToTuple,
    Tuples.Map<Numbers.Div<T, _>>,
    Tuples.Map<PartialApply<PPowFn, [R, _, P]>>,
    Tuples.Every<Numbers.NotEqual<1>>,
  ]
>;

// 原始根を求める
// P: 素数
type PrimitiveRoot<
  P extends number,
  R extends number = 1,
  T extends number = Call<Numbers.Sub<P, 1>>,
> =
  IsPrimitiveRoot<P, R, T> extends true
    ? R
    : PrimitiveRoot<P, Call<Numbers.Add<R, 1>>, T>;

// 小さい値
export type r1 = PrimitiveRoot<5>; // 2
export type r2 = PrimitiveRoot<17>; // 3
export type r3 = PrimitiveRoot<97>; // 5

// 時々見かける値
export type R1 = PrimitiveRoot<998244353>; // 3
export type R2 = PrimitiveRoot<167772161>; // 3
export type R3 = PrimitiveRoot<469762049>; // 3

参考

https://37zigen.com/primitive-root/