NTT、原根

cjoierzdc / 2023-05-14 / 原文

原根

定义

  • 阶:\(\delta_{mod}a\) 为最小的 \(x\) 满足 \(a^x\equiv1\pmod {mod}\)
  • 原根:若 \(x,mod\) 满足 \(\delta_{mod}x = \varphi (mod)\) 时,\(x\)\(mod\) 的一个原根。

性质

  • \(mod\) 有原根的充要条件:\(mod = 2,4,p^k,2p^k\)\(p\)奇质数

### 求一个数的所有原根