原根（2）

2019-04-14 08:21发布

站内文章 / 模拟电子
14675 0 1638
class="markdown_views prism-tomorrow-night">

对于两个正整数gcd(a,m)=1，由欧拉定理可知，存在正整数 d ≤ m-1， 比如说欧拉函数 d=φ(m)，即小于等于 m的正整数中与 m互素的正整数的个数，使得 ad≡1(mod m)。
由此，在gcd(a,m)=1时，定义 a对模m的指数 δm(a)为使 ad≡1(mod m) 成立的最小的正整数 d。由前知 δm(a) 一定小于等于 φ (m)，若δm(a) = φ(m)，则称a是模 m的原根。 另一种定义
假设一个数g对于P来说是原根，那么gi mod P的结果两两不同,且有 1 < g < P, 1 < i < P，那么g可以称为是P的一个原根
简单来说，gi mod p ≠ gj mod p （p为素数），其中i≠j且i, j介于1至(p-1)之间，则g为p的原根。 简单的来说，如果g是P的原根，那么g的（1…P-1）次幂mod P的结果一定互不相同。 例如：
设m= 7，则φ（7）等于6。φ（7）表示7的欧拉函数。
设a= 2，由于23=8≡1(mod 7)，而3<6，所以 2 不是模 7 的一个原根。
设a= 3，由于31≡3(mod 7)，32≡2(mod 7)，33≡6(mod 7)，34≡4(mod 7)，35≡5(mod 7)，36≡1(mod 7)，所以 3 是模 7 的一个原根。

如何求解：

一、枚举 从2开始枚举，然后暴力判断g(P-1) ≡ 1 (mod P)是否当且当指数为P-1的时候成立
而由于原根一般都不大，所以可以暴力得到.
二、讲究方法
例如求任何一个质数x的任何一个原根，一般就是枚举2到x-1，并检验。有一个方便的方法就是，求出x-1所有不同的质因子p1,p2…pm，对于任何2<=a<=x-1,判定a是否为x的原根，只需要检验a((x-1)/p1),a((x-1)/p2),…a((x-1)/pm)这m个数中，是否存在一个数mod x为1，若存在，a不是x的原根，否则就是x的原根。
原来的复杂度是O(P-1)，现在变成O(m)*log（P-1）m为x-1质因子的个数。很明显质因子的个数远远小于x-1。
证明可用欧拉定理和裴蜀定理： 裴蜀定理
说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：
ax + by = m
有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。
例如，12和42的最大公因子是6，则方程12x + 42y = 6有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。
特别来说，方程 ax + by = 1 有解当且仅当整数a和b互素。
裴蜀等式也可以用来给最大公约数定义：d其实就是最小的可以写成ax + by形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。 证明
假设存在一个t < phi(x)=x-1使得at ≡ 1 (mod x)
那么由裴蜀定理，一定存在一组k,r使得kt=(x-1)r+gcd(t,x-1)
而由欧拉定理有，a(x-1) ≡ 1 (mod x)
于是1 ≡ a(kt) ≡ a(xr-r+gcd(t,x-1)) ≡ agcd(t,x-1) (mod x)
而t < x-1故gcd(t,x-1) < x-1
又gcd(t,x-1)|x-1 于是gcd(t,x-1)必整除(x-1)/p1,(x-1)/p2…(x-1)/pm其中至少一个，设其一为(x-1)/pi
那么a((x-1)/pi) ≡ (agcd(t,x-1))s ≡ 1s ≡ 1 (mod x)
这与假设矛盾 模板 vector a; ll pow_mod(ll a, ll i, ll n){ if (i == 0){ return 1%n; } int tmp = pow_mod(a, i>>1, n); tmp = tmp * tmp % n; if (i&1){ tmp = tmp * a % n; } return tmp; } bool g_test(ll g, ll p) { for (ll i = 0; i < a.size(); i++){ if (pow_mod(g, (p-1)/a[i], p) == 1){ return 0; } } return 1; } ll primitive_root(ll p){ a.clear() ; ll tmp = p-1; for (ll i = 2; i <= tmp; i++) { if (tmp%i == 0){ a.push_back(i); while(tmp%i == 0){ tmp /= i; } } } if (tmp != 1){ a.push_back(tmp); } ll g = 1; while(true){ if (g_test(g, p)){ return g; } g++; } }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
关于原根个数问题
以下内容来自知乎
对于正整数 gcd(a,m)=1，如果a是模m的原根，那么a是整数模m乘法群的一个生成元，由于又φ(m)个元素，而它的生成元就是他的可逆元的数目即φ(φ(m))。 “生成元的个数等于可逆元的数目”指的是 Z/ϕ(m)Z 这个群中可逆元的个数。 因为a 是 (Z/mZ)^{×}的生成元。 所以 (Z/mZ)^{×}同构于循环群（Z/ϕ(m)Z，+）。 而(Z/mZ)^{×}的原根对应过来就是Z/ϕ(m)Z的生成元。 而Z/ϕ(m)Z的生成元就是Z/ϕ(m)Z中×的可逆元。 所以一共是ϕ(ϕ(m))个。 ——————分割线————————
poj-1284 Primitive Roots #include #include #include #include #include #include #include #include #define N 1010 using namespace std; const int Max = 65540; int minDiv[Max], phi[Max], sum[Max]; void getPhi() { for (int i = 1; i < Max; i++) { minDiv[i] = i; } for (int i = 2; i*i < Max; i++){ if (minDiv[i] == i){ for (int j = i*i; j < Max; j += i){ minDiv[j] = i; } } } phi[1] = 1; for (int i = 2; i < Max; i++) { phi[i] = phi[i / minDiv[i]]; if ((i / minDiv[i]) % minDiv[i] == 0){ phi[i] *= minDiv[i]; } else { phi[i] *= minDiv[i] - 1; } } } int main() { #ifndef ONLINE_JUDGE freopen("1.txt", "r", stdin); #endif ios::sync_with_stdio(false); cin.tie(0); getPhi(); int p; while(cin >> p){ cout << phi[p-1] << endl; } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
转载自：https://blog.csdn.net/qq_21120027/article/details/52832543

热门文章