Zenn
メディカルフォース テックブログPublicationへの投稿
🚀

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

rryyoo
2025/01/08に公開
TypeScript
型
原始根
繰り返し2乗法
hotscript
tech

導入

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

なんか 1 になります！

あけおめなので、抱負

ん〜、

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

とかですかね

原始根

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

一般には、p を素数とすると、適当に r を取れば

\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}

r を p に対応する原始根と言います

p = 5, r = 2 の場合

\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}

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

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

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

原始根の計算方法

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

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

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

r^\frac{p - 1}{q_i} \not\equiv 1 \quad (\mathrm{mod} \ p) \qquad (1 \le i \le k)

が成り立てば r は p に対応する原始根になる

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

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

r = 2 では
r^\frac{96}{2} = r^{48} = 281474976710656 \equiv 1 \quad (\mathrm{mod} \ 97) \qquad \to \text{ダメ}

r = 3 では
r^\frac{96}{2} = r^{48} = 79766443076872509863361 \equiv 1 \quad (\mathrm{mod} \ 97) \qquad \to \text{ダメ}

r = 4 では
r^\frac{96}{2} = r^{48} = 79228162514264337593543950336 \equiv 1 \quad (\mathrm{mod} \ 97) \qquad \to \text{ダメ}

r = 5 では
\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 = 5 は p = 97 に対応する原始根なことがわかりました

繰り返し 2 乗法

前節で 3^{48} を 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}

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

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

\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}

そして 48 を 48 = 16 + 32 と 2 進展開すると
3^{48} = 3^{16 + 32} = 3^{16} \cdot 3^{32} \equiv 61 \cdot 35 = 2135 \equiv 1 \quad (\mathrm{mod} \ 97)

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

最後に "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/

メディカルフォース テックブログ
メディカルフォース テックブログPublication

Discussion