算法学习笔记(11): 原根

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6

    原根

    此文相对困难,请读者酌情食用

    在定义原根之前,我们先定义其他的一点东西


    通俗一点来说,对于 \(a\) 在模 \(p\) 意义下的就是 \(a^x \equiv 1 \pmod p\)最小正整数解 \(x\)

    或者说,\(a\) 在模 \(p\) 意义下生成子群的阶(群的大小)

    再或者说,是 \(a\) 在模 \(p\) 意义下的循环节的大小

    循环节,生成子群……真绕……其实两者很类似

    两者的大小也就是在模 \(p\) 意义下集合 \(\{a^1, a^2, a^3,\dots,a^k\}\) 不重复元素的个数

    可以通过欧拉定理可知 \(a^{\varphi(p)} \equiv a^0 \equiv 1 \pmod p\) 也就是说存在一个数 \(k\),使得 \(a^k \equiv a \pmod p\)

    所以,就有了循环……

    我们将 \(a\) 在模 \(m\) 意义下的记作 \(ord_ma\)

    显然,无论是根据群论还是什么,\(ord_ma\) 一定是 \(\varphi(p)\) 的因数

    特别的,当 \(ord_ma = \varphi(p)\) 时,称 \(a\) 为模 \(p\) 意义下的一个原根

    那么原根的定义出来了……


    原根

    上述定义或许不是那么简单,我们换一种说法

    \[\begin{aligned} \forall x \in [1, \varphi(p)), a^x \not\equiv 1 \pmod p \\ a^{\varphi(p)} \equiv 1 \pmod p \end{aligned} \]

    满足上述两个条件的数 \(a\) 就是模 \(p\) 意义下的一个原根

    这两个条件也是我们在程序中验证原根的方法 QwQ

    而对于原根来说,\(a^1, a^2,\dots,a^{\varphi(p)}\)\(m\) 下各不相同,他们就是最短的循环节,也是模 \(p\) 意义下的完全剩余系,或者说原根的生成子群


    但是,并不是每一个数都存在原根

    例如 \(\varphi(8) = 4\),但是没有任何数在模 \(8\) 下的阶为 \(4\)

    为判断一个数是否有原根,我们有一个重要的定理:

    正整数 \(k\) 有原根的充要条件为 \(k\) 能表示成 \(2, 4, p^n, 2p^n\) 中的任何形式之一,其中 \(p\)为奇素数

    由于证明比较复杂,若感兴趣可以参见这篇博客 原根证明


    那么如何求出一个数 \(p\) 有多少个原根

    假设我们已经求出了一个原根 \(g\)

    由于原根一定存在与 \(p\) 的完全剩余系中,而 \(g\) 的生成子群与之等价,也就是说,我们需要在

    \[\{g^k|k \in [1, \varphi(p))\} \]

    这个集合中寻找所有的原根

    所以,考虑构造出判断阶的方法。我们令 \(d = gcd(k, \varphi(p))\)

    那么

    \[g^{k\frac {\varphi(p)} d} \equiv g^{\varphi(p) \frac kd} \equiv 1^{\frac kd} \equiv 1 \pmod p \]

    那么 \(\frac k{gcd(k, \varphi(p))}\) 也就是 \(g^k\) 的阶

    若需要满足原根的定义,我们必须使得 \(gcd(k, \varphi(p)) = 1\)

    同时考虑 \(g = g^1\)\(gcd(1, \varphi(p)) = 1\),也就是说有总共有 \(\varphi(\varphi(p))\) 个原根


    这同时启发我们,只要我们找到了任意一个模 \(p\) 意义下的原根,我们就可以求出所有原根。

    至于如何找到原根,选择暴力枚举即可

    有证明:如果一个数 \(n\) 有原根,则其最小原根渐近意义下不大于 \(\sqrt[4]n\) 级别,所以直接枚举是没有任何问题的


    那么我们总结一下求 \(n\) 的原根的所有步骤

    • 预处理

      • 利用线性筛求出所有的质数以及每一个数的 \(\varphi\)

      • 对每一个筛出的质数,标记出所有 \(p^q\)\(2p^q\) (别忘了\(2, 4\))

    • 判断 \(n\) 是否有原根

    • 最小原根

      • 求出 \(\varphi(m)\) 的所有质因数 \(i\),记录 \(m/i\) (记得将 \(1\) 也记录进去)

      • 枚举一个数 \(g\),对于每一个记录的数 \(j = m/i\) 分别计算 \(g^j\),如果\(i^j \equiv 1 \pmod m\) ,说明 \(i\) 不是原根 (这里再下文中有解释)

      • 重复第二部,直到找到一个原根 \(g\) 为止

    • 所有原根

      • 枚举 \(k \in [1, \varphi(m))\)

      • 如果 \(gcd(k, \varphi(m)) = 1\),则 \(g^k\) 一个原根,记录下他

    解释:求最小原根的判断

    为什么我们只需要枚举 \(m/i\) 就行了?

    考虑我们将 \(m\) 分解成 \(m = i_1^{a_1} i_2^{a_2}\dots i_k^{a_k}\)

    由于如果需要满足 \(i^j \equiv 1 \pmod p\),一定有 \(j|\varphi(p)\)

    那么对于 \(m/i = kj\),一定有 \(i^{m/i}\equiv 1 \mod p\)

    也就是说,所有 \(m/i\) 就包含了所有情况了

    那么为什么要加上 \(1\) 呢,这就交给读者消化思考喽 _

    参考代码如下:真的只供参考,这种写法特别慢

    template<typename T>
    inline T gcd(T x, T y) {
    	T z;
    	while (y) z = x % y, x = y, y = z;
    	return x;
    }
    
    template<typename T>
    inline T qpow(T a, T x, T p) {
    	T r(1); a %= p;
    	while (x) {
    		if (x & 1) r = (r * a) % p;
    		a = (a * a) % p, x >>= 1;
    	}
    	return r;
    }
    
    int phi[N], notp[N];
    std::vector<int> prm;
    void getPrm() {
    	phi[1] = 1;
    	for (int i = 2; i < N; ++i) {
    		if (!notp[i]) prm.push_back(i), phi[i] = i - 1;
    		
    		for (const int &j : prm) {
    			if (i * j >= N) break;
    			notp[i * j] = true;
    			if (i % j == 0) {
    				// i | n && i^2 | n => phi(n) = phi(n / i) * i
    				phi[i * j] = phi[i] * j; break;
    			} else {
    				// i | n && not i^2 | n => phi(n) = phi(n / i) * (i - 1)
    				phi[i * j] = phi[i] * phi[j];
    			}
    		}
    	} // end getPrm for
    }
    
    bool exists[N];
    void getExists() {
    	exists[2] = exists[4] = true;
    	for (int i = 1; i < (int)prm.size(); ++i) {
    		int p = prm[i];
    		for (int q = p; q < N; q *= p) {
    			exists[q] = true;
    			if (q * 2 < N) exists[q * 2] = true;
    		}
    	}
    	// printf("Exists init!\n");
    }
    
    void factorize(int x, vector<int> & v) {
    	v.push_back(1);
    	for (const int &p : prm) {
    		if (p >= x) break;
    		if (x % p == 0) v.push_back(x / p);
    	}
    }
    
    void getAll(int p, vector<int> & v) {
    	// no answer
    	if (!exists[p]) return;
    	
    	int ph = phi[p];
    	int fst, cur;
    	vector<int> factors; factors.clear();
    	factorize(ph, factors);
    	
    	// enum i which gcd(i, m) == 1
    	// find first element i suit i^ph = 1 mod p
    	for (int i = 1; ; ++i) {
    		if (gcd(i, p) != 1) continue;
    		// if (qpow(i, ph, p) != 1) continue;
    		
    		bool valid = true;
    		// we need i only if i^ph = 1 mod p, not other numbers.
    		for (auto &e : factors) {
    			if (e != ph && qpow(i, e, p) == 1) {
    				valid = false; break;
    			}
    		}
    		
    		if (valid) {
    			fst = cur = i; break;
    		}
    	}
    	
    	for (int i(1); i <= ph; ++i) {
    		if (gcd(i, ph) == 1) v.push_back(cur);
    		cur = cur * fst % p;
    	}
    }
    

    考虑模板可能有爆 int 的风险,请参考者合理使用 long long

    这样通过 getAll 得出的 vector 是乱序的,需要再排序一次

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6