Posts match “ 离散对数 ” tag:

原根:定义见 wiki,这里只补充讲解数 的原根的求法.

首先我们肯定要从 开始枚举 的原根 (或者rand()),关键在于怎么验证某一个数是不是一个原根:

  1. 最暴力的方法就是暴力枚举 范围内的指数,看有是不是所有结果都不模 .
  2. 优化:我们可以只枚举 的因子,因为 的阶 满足 .
    反证:若 ,则设 ,这里 .
    那么 ,这与 矛盾.
  3. 继续优化:我们可以只枚举 的质因子 ,如果 ,那么 是模 的原根.
    还是反证:在 的情况下,若 不是模 的原根,那必然有 .
    由 2 知 ,故设 ,再设 的一个因子,那同时 也是 的一个因子,所以 ,矛盾.

这样求原根就会非常之快了.

未完待续。。。