原根
阶
若 ,使 成立的最小的 ,称为 关于模 的阶,记为 。
若 ,则
由欧拉定理,设 ,则 当且仅当 ,特别地, 。
- 设 是素数, ,那么有且仅有 个关于模 的阶为 且两两互不同余的数。
- 设 ,则 关于模 两两互不同余。
- 设 是素数, ,则存在 个关于模 的阶为 且两两互不同余的数。
- 若 ,则
原根
,若 ,则称 为 的一个原根。
为 的一个原根当且仅当 构成模 的一个既约剩余系。
判断是否有原根
若 有原根,则 一定是下列形式: 。这里 为奇素数, 为正整数。
求一个原根
,设 是 的所有不同的素因数,则 是 的原根,当且仅当对任意 ,都有 。
证明
假设存在一个 使得 且 。
由裴蜀定理得,一定存在一组 满足 ;由欧拉定理/费马小定理得 ;故有:
又有 ,故 。
又 ,故 必至少整除 中的至少一个,设 ,则 。
故假设不成立。
求所有原根
设 为 的一个原根,则集合 给出 的全部原根。因此,若 有原根,则 有 个关于模 两两互不同余的原根。
一个数的最小原根
若一个数 存在原根,可以证明 的最小原根在 级别。
这个结论意味着,我们求所有的原根时,枚举最小原根花费的时间一般都是可以接受的。
用途
我们发现原根 拥有所有 DFT 所需的单位根 的性质,于是我们用 来代替 ,理论上就能把复数对应到一个整数,在模 意义下进行快速变换了。
但实际上由于快速傅里叶变换(FFT)实现的多项式乘法的过程中要求序列长度是 的幂次,因此这里模数 还需要保证 的标准分解式中素因子 的幂次足够大,参见 快速数论变换 。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用