补充一下attackNTT题解的一个证明

若 $P$ 为素数，假设一个数 $g$ 是 $P$ 的原根，那么 $g^i \mod P(1<g<P,0<i<P)$ 的结果两两不同。

不要问我为什么，因为我也不知道。。

这其实是好证的。
阶的定义是若存在最小的正整数

i

满足

a^i\equiv1 (\mod n)

，则称

i

为

a\mod n

的阶。原根的定义题解里有。

有一个定理: 不存在

0<j<k\le \phi (n)

满足

j\in \mathbb{N^*}

，

k\in \mathbb{N^*}

，

a

是

n

的原根且

a^j\equiv a^k(\mod n)

考虑证明。

首先

a^{\phi (n)} \mod n=1

。考虑反证法。如果存在，那么

a\mod n

的阶就是

k-j< \phi (n)

，这不满足与原根的定义。

因为不存在，且

P

是素数，所以

\phi (P)=P-1

，所以两两不同。

讨论操作