千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2022年8月実施 専門 B10

标签：

• Prime-Factorization
• Algorithm-Complexity

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

素数 $p$ に対し $p-1=\prod_{i=1}^kp_i^{e_i}$ を素因数分解とする。

1. $g\in(\mathbb Z/p\mathbb Z)^\times$ が生成元であるための必要十分条件は、すべての $i$ に対して $g^{(p-1)/p_i}\not\equiv1\pmod p$ であることを示せ。
2. $p,g$ と $p-1$ の素因数分解が与えられれば、$g$ が生成元かどうかを $p$ の二進表記長の多項式時間で判定できることを示せ。

题目描述

设 $p$ 为素数，已知 $p-1$ 的素因数分解。(1) 证明本原根判据：对每个素因子 $p_i$，都有 $g^{(p-1)/p_i}\not\equiv1\pmod p$；(2) 说明该判据能在输入位数的多项式时间内检验。

Kai

(1) $d=\operatorname{ord}(g)$ とすると $d\mid p-1$。$d=p-1$ なら、より小さい正の指数 $(p-1)/p_i$ で $1$ にはならない。逆に $d<p-1$ なら、整数 $(p-1)/d>1$ の素因子 $p_i$ をとれる。このとき $d\mid(p-1)/p_i$ なので $g^{(p-1)/p_i}=1$。従って必要十分条件が従う。

(2) $L=\lceil\log_2p\rceil$ とする。異なる素因子数は高々 $L$。各指数は $p$ 未満なので、繰り返し二乗法による一回の冪剰余計算には $O(L)$ 回の乗算・剰余演算で足りる。通常の筆算で $L$ ビット整数の乗算・剰余は $O(L^2)$ ビット演算だから、全検査は $O(L^4)$ ビット演算以内で終了する。素因数分解は入力として与えられているため、その計算時間は不要である。$p=2$ では空の条件を満たす唯一の元 $1$ が生成元である。