原根计算及应用

引言:今天上课老师讲了这个,但是信息量有点大,没有很好的理解,先把它放在博客上,以后再学习。

同余基本知识

  • 模和同余:设 $a$ 、$b$ 和 $m$ 均为整数,且 $m>0$ 。如果 $a$ 和 $b$ 被 $m$ 除所得的余数相同,那么称 $a$ 和 $b$ 关于模 $m$ 是同余的,记作
    $$a \equiv b(mod \; m)$$
  • 几个等价定义:
  • $a$ 和 $b$ 关于模 $m$ 是同余的:
    $$a=mq_1+r \quad b=mq_2+r$$

$$a \equiv b(mod \; m)$$

  • $b-a$ 能被 $m$ 整除,记 $m|a-b$
    $$a-b\equiv 0(mod \; m)$$

同余性质

  • $a \equiv a(mod \; m)$
  • $a \equiv b(mod \; m) \Longrightarrow b \equiv a(mod \; m)$
  • $a \equiv b(mod \; m) \quad b \equiv c(mod \; m) \Longrightarrow a \equiv c(mod \; m)$
  • 设$a \equiv b(mod \; m)$,$b \equiv c(mod \; m)$,那么
    $$ac \equiv bd(mod \; m)$$

$$ac \equiv bc(mod \; m)$$
$$a^n \equiv b^n(mod \; m)$$

  • 费马小定理:设 $a$ ,$p$ 为正整数,且 $p$ 为素数,$gcd(p,a)=1$ ,那么
    $$a^{p-1} \equiv 1(mod \; p)$$

原根与离散对数

  • 原根与离散对数是数论中的一个重要内容
  • 给定正整数 $m$ ,正整数 $a$,$b$,$gcd(a,m)=gcd(b,m)=1$ ,求最小的非负整数 $x$ ,使得 $a$$x$ $≡$ $b$ $(mod$ $m)$ 。
  • 原根: 给定整数 $m$ ,$g$ , $gcd(g,m)=1$ ,若满足$g^x$ $≡$ $1$ $(mod$ $m)$ 的最小正整数 $x=φ(m)$ ,则 $g$ 即为模 $m$ 的原根。

剩余类与既约剩余系

  • 剩余类:对于整数 $a$ 及模 $m$ ,则集合$A=\{ \;x\; | \;x≡ a (mod\; m) \;\}$ 称为模 $m$ 关于 $a$ 的一个剩余类。
  • 完全剩余系:$\{0,1,2,…,m-1\}$ 是一个特殊的集合,元素个数 $m$ ,其中任何两个数都不同余,称为完全剩余系。
  • 任何 $m$ 个元素的集合 $X$ ,如果其中任何两个数都不同余,那么 $X$ 也是一个完全剩余系。
  • 既约剩余系:设 $m$ 为正整数,在与 $m$ 既约的所有剩余类中,每一个类中取一个数,构成一个集合 $X$ ,则 $X$ 称为模 $m$ 的一个简化剩余系。
  • 既约剩余系的有 $r=φ(m)$ 个元素。
举例
1:若p是素数,则{1,2,3,…,p-1}是模p的一个既约剩余系。
2:{1,5,7,11}是模12的一个既约剩余系。
  • 结论:模 $m$ 的既约剩余系的 $φ(m)$ 个元素对模 $m$ 乘法构成一个群。

模方程

$a \equiv b(mod \; m)$ 相当于求 $ax+my=b$

根据前面求 $ax+my=b$ 的步骤:

  • 求 $d=gcd(a,m)$ ,写 $a=da_0$ ,$m=dm_0$
  • 若 $d \nmid b$ ,则 $a \equiv b(mod \; m)$ 无解;否则,$a \equiv b(mod \; m)$ 有 $d$ 个点。
  • 由 $ax_0+my_0=d$ ,改写为 $x=x_0\;\frac{b}{d}$ ,$y=y_0\;\frac{b}{d}$
  • $a \equiv b(mod \; m)$ 的所有解可写为:
    $$x=(x_0\;\frac{b}{d}+i\;\frac{m}{d})mod\; m,i=0,1,2,...,d-1$$

欧拉定理与费尔玛小定理

  • 欧拉定理:设 $m$ 是大于 $1$ 的整数,整数 $a$ 与 $m$ 互质,即 $(a,m)=1$ ,则 $a^{φ(m)}\equiv1(mod \; m)$;这里,$φ(m)$ 是欧拉函数,即它是正整数 $1,2,…,m$ 中与 $m$ 互质的数的个数。
  • 费尔玛小定理:设 $p$ 为素数,整数 $a$ 与 $p$ 互质,即 $(a,p)=1$ ,则 $a^{p-1} \equiv 1(mod \; p)$ 。一般地,对任何整数 $a$ ,均有则 $a^p \equiv a(mod\ p)$。

快速模幂运算

  • 模幂运算—快速计算法
  • 将 $r$ 化为二进制数 $(b_kb_{k-1}…b_2b_1b_0)$ 的形式,然后反复平方取余数。然后从最低位开始,自右至左逐位扫描。每次迭代时.用到下面两个恒等式中的。

$$a^{2c}mod\ m=(a^2)^cmod\ m$$
$$a^{2c+1}mod\ m=a*(a^2)^cmod\ m$$

  • 代码
long modular_power1(long a, long r, long m){
  long d, t;
    d=1;t=a;   
    while (r>0){   
      if ((r%2)==1) d=(d*t) % m;
      r=r/2;
      t=t*t % m;
    }
    return d;
}

原根

(一)原根有关概念

  • :设 $m$ 是正整数,$a$ 是整数,若有正整数 $r$ 使得,$a^r \equiv 1(mod \; m)$,但对于任何 $i$ ,$1 \leq i<r$ ,均有$a^i \equiv 1(mod \; m)$ ,那么称 $r$ 为 $a$ 模 $m$ 的阶。记$r=ord_m(a)$ ,也记为 $\delta_m(a)$
  • 若 $r$ 为 $a$ 模 $m$ 的阶,则对任何 $i$ , $0 \leq i<r$,那么 $a_i(mod \ m)$ 的结果两两不同。
  • 性质:设正整数 $a$ 与 $m$ 互质,即 $gcd(a,m) = 1$ 。对正整数 $d$ ,若 $a_d≡1(mod \ m)$ ,则 $\delta_m(a)$ 整除 $d$ 。

原根

  • 设 $m$ 是正整数,$g$ 是整数,若 $g$ 模 $m$ 的阶等于 $φ(m)$ ,则称 $g$为模 $m$ 的一个原根。(其中 $φ(m)$ 表示 $m$ 的欧拉函数),特别地,若 $m$ 为素数 $p$ ,若 $g$ 模 $p$ 的阶等于 $p-1$ ,那么 $g$ 为模 $p$ 的一个原根。

举例

  • 例1. p=7
    $1$到$6$中的任何数均与$p$互质;取$g=3$,那么$3^0\equiv 1,3^1\equiv 3,3^2\equiv 2,3^3\equiv 6,3^4\equiv 4,3^5\equiv 5,3^6\equiv 1(mod \; 7)$(重复);所以$g=3$为原根。
  • 例2. p=11
    $1$到$10$中的任何数均与$p$互质;取$g=3$,那么$3^0\equiv 1,3^1\equiv 3,3^2\equiv 9,3^3\equiv 5,3^4\equiv 4,3^5\equiv 1 (mod \; 11)$(重复),$r=5\neq 10$ ;所以$g=3$不为原根。

取$g=3$,那么$3^0\equiv 1,3^1\equiv 3,3^2\equiv 9,3^3\equiv 5,3^4\equiv 4,3^5\equiv 1 (mod \; 11)$(重复),$r=5\neq 10$ ;所以$g=3$不为原根;类似地$g=4$也不为原根。
$1$到$10$中的任何数均与$p$互质;取$g=7$,那么$7^0\equiv 1$,$7^1\equiv 7$,$7^2\equiv 5$,$7^3\equiv 2$,$7^4\equiv 3$,$7^5\equiv 10$,$7^6\equiv 4$,$7^7\equiv 6$,$7^8\equiv 9$,$7^9\equiv 8$,$7^{10}\equiv 1$ $(mod \; 11)$(重复),$r=10=p-1$ ;所以$g=7$为原根。

原根的性质

  • 设正整数 $a$ 与 $m$ 互质,即 $gcd(a,m) = 1$ 。对正整数 $d$ ,若 $a^d≡1(mod \; m)$ ,则 $\delta_m(a)$ 整除 $d$ ,特别地,$\delta_m(a)$ 整除 $φ(m)$ 。应用:在 $p=7$ 例子中,当 $a= 3$ 时,我们仅需要验证 $3$ 的 $1$ 、$2$ 、$3$ 次方模 $7$ 的余数即可,如有余数为 $1$ ,那么 $a$ 不是模 $p=7$ 的原根。
  • 记 $r = \delta_m(a)$ ,则 $a_1, a_2,..., a_{r-1} (mod \; m)$ 两两不同余。因此当 $a$ 是模 $m$ 的原根时,$a_0,a_1,… ,a_{r-1}$ 构成模 $m$ 的简化剩余系。
  • 模 $m$ 有原根的充要条件是 $m= 1、2、4、p、2p、p^n$ ,其中 $p$ 是奇质数,$n$ 是任意正整数。(证明略)
  • 对正整数 $a$ ,设 $gcd(a,m) = 1$ 。如果 $a$ 是模 $m$ 的原根,那么 $a$ 是整数模 $m$ 乘法群 $Zm^*$ 的一个生成元,即 $Zm^*$ 的元素 $x$ 均可以表示为 $a$ 的幂,$x=a^k$ 。
  • $Zn$ 有 $r=φ(m)$ 个元素,如果 $g$ 是生成元,那么 $1=g^0$ ,$g^1$ ,$g^2$ , ……,$g^{r-1}$ 互不相同(mod m下)。
    注:
  • 所有整数在模 $m$ 下所有余数相同的数构成一个等价类(称为同余类);所有同余类取一个代表构成一个集合,实际上是整数集 $Z$ 模 $m$ 构成的商集合 $Z/mZ$ 。
  • 所有与 $m$ 互质的正整数构成的等价类构成的集合 $Zm^*$ 构成一个乘法群 $Zn$ 。$Zn$ 有 $φ(m)$ 个元素。
    (1) 上述 $r=φ(m)$ 个元素中, $g^t$ 能够成为生成元,其充分必要条件是 $t$ 与 $φ(m)$ 互质。在 $1$ 到 $r$ 中与 $r$ 互质的个数为 $φ(r)$ ;(2) 若 $Zn$ 有生成元,那么个数为 $φ(φ(m))$ 个;
  • 若模 $m$ 有原根,则它有 $φ(φ(m))$ 个原根。
  • 如果 $p$ 为素数,那么素数 $p$ 一定存在原根,并且模 $p$ 的原根个数为 $φ(p-1)$ 。

原根的判断

(1) 按定义判定:$g$ 的阶 $r= φ(m)$

(2) 设 $p$ 为素数:

  • 设一个数 $g$ 是与 $p$ 互质的整数,$p$ 为模 $p$ 的原根,当且仅当,$g^i \; mod \; p$ $(0 \leq i<p-1)$ 的结果两两不同(两两不同余)。
    即:$g^i mod \; p$ $≠$ $g^j mod \; p$ ( $p$ 为素数),$i≠j$ ,$0<i$ , $j<p-1$ 。
  • 设一个数 $g$ 是与 $p$ 互质的整数,$g$ 为模 $p$ 的原根,当且仅当,$g^r \equiv 1 (mod \; p)$ 仅在 $r=p-1$ 时成立、而在 $0<r<p-1$ 时不成立。

:以后为了描述方便起见,将 $a$ 的生成元 $g$ 表示 $a \equiv g^x (mod \; p)$ 直接表示成 $a=g^x$ ,其实在群的观点下是合理的。

原根求法

(1) 求原根目前的做法只能是从 $2$ 开始枚举,然后暴力判断 $g^{p-1} \equiv 1 (mod \; p)$ ,是否当且仅当指数为 $p-1$ 的时候成立。如成立,则为原根。由于原根一般都不大,所以可以暴力得到。

(2) 求素数 $p$ 模原根的方法:对 $p$ 求素因子分解,即是的标准分解式
$$p-1=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$$
若恒有
$$g^{ \frac{p-1}{p_i}} \neq 1(mod \; p),i=1,2...k$$
成立,则 $g$ 就是 $p$ 的原根。

原根求法举例

$p=47$ 是素数,求 $p$ 的原根。

  • $r=p-1=46=2×23$( $2$ 和 $23$ 都是素数),那么,$p=47$ 的原根 $g$ 需满足 $g^{p-1} \equiv 1(mod \; p)$,但 $g^2 \neq 1$ $(mod \; p)$,且 $g^{23} \neq 1$ $(mod \; p)$。原根个数 $φ(r)= φ(46)=22$ 。模 $47$ 的非二次剩余有:$3$ , $5$ , $6$ ,$10$ , $11$ , $12$ , $14$ , $17$ , $19$ , $21$ , $22$ , $24$ , $27$ , $29$ , $31$ , $32$ , $34$ , $38$ , $39$ , $40$ , $43$ , $45$ ,正好 $22$ 个,这些就是模 $47$ 的原根。

求原根的程序

#include <iostream>  
#include <string.h>  
#include <algorithm>  
#include <stdio.h>  
#include <math.h>  
#include <bitset>    
using namespace std;  
typedef long long LL;    
const int N = 1000010;    
bitset<N> prime;  
int p[N],pri[N];  
int k,cnt;
void isprime() {  //素数表构建
    prime.set();  
    for(int i=2; i<N; i++) {  
        if(prime[i]){  
            p[k++] = i;  
            for(int j=i+i; j<N; j+=i)  prime[j] = false;  
        }  
    }  
}    
void Divide(int n) {  //求n的所有的质因子 
    cnt = 0; int t = (int)sqrt(1.0*n);  
    for(int i=0; p[i]<=t; i++) {  
        if(n%p[i]==0) {  
            pri[cnt++] = p[i];  while(n%p[i]==0) n /= p[i];  
        }  
    }  
    if(n > 1) pri[cnt++] = n;  
}
LL quick_mod(LL a,LL b,LL m){//快速幂计算  
    LL ans = 1;  
    a %= m;  
    while(b) {  
        if(b&1){  
            ans = ans * a % m;  
            b--;  
        }  
        b >>= 1;  
        a = a * a % m;  
    }  
    return ans;  
}
int main(){  
    int p;  isprime();  
    while(cin>>p) {  
        Divide(p-1);  
        for(int g=2; g<p; g++) {  
            bool flag = true;  
            for(int i=0; i<cnt; i++) {  
                int t = (p - 1) / pri[i];  
                if(quick_mod(g,t,p) == 1) {  flag = false;  break;  }  
            }  
            if(flag) {  
                int root = g;  
                cout<<root<<endl;  
            }  
        }  
    }  
    return 0;  
}

例题

Description

We will give you a non-negative integer $m$ and a prime number $p$ . And we define $f(i)$ is the number of pair( $x,y$ ) that satisfies $(x+y)^i≡x^i \% p$ and $1≤x≤p−1,1≤y≤m$ . Now, you have to calculate the sum. Maybe the sum is too big, so you only need to output the sum $\sum^{p-1}_{i=0} if(i)$ after mod $1e9+7$ .

Input

The first line contains only one integer $T$ , which indicates the number of test cases.
For each test case, there are a integer $m(1≤m≤p−1)$ and a prime number $p(2≤p≤1e9+7)$ on one line.

Output

For each test case, output one line "Case #x: y" , where x is the case number (starting from $1$ ) and $y$ is the sum after mod $1e9+7$ .

Sample Input

3
5 7
3 11
2 103

Sample Output

Case #1: 210
Case #2: 390
Case #3: 50388

题意

给定正整数 $m>0$ 和素数 $p$ 。记 $f(i)$ 为满足条件 $(x+y)^i≡x^i \% p$ 及 $1≤x≤p−1、1≤y≤m≤p−1$ 的数对 $(x,y)$ 的组数。你的任务是计算和
$\sum^{p-1}_{i=0} if(i)(mod \; 10^9+7)$ 。

分析

本题要求满足 $(x+y)^i≡x^i \%p$ ,$1≤x≤p−1$、$1≤y≤m≤p−1$ 的数对 $(x,y)$ 个数。直接去求 $x,y$ 不现实,但可以计算个数。对于素数 $p$ ,有原根 $g$ ,$g$ 也是生成元,即 $1$ 到 $p-1$ 的任何整数 $k$ 都可以用 $g$ 的幂 $g^t$ 表示,$0 \leq t<p-1$ 。现在,对于满足 $1≤x≤p−1$ 的 $x$ ,由于 $x$ 与 $p$ 互质,因此 $x$ 可写成 $x=g^u$ ;类似地,$y$可写成 $y=g^v$ ,$0≤u$ ,$v≤p-2$。

将 $x=g^u,y=g^v$ 代入 $(x+y)^i \equiv x^i(mod \; p)$ ,可得 $(g^u+g^v)^i \equiv g^{ui} (mod \; p)$. 变形为
$$[g^u(1+g^{v-u})]^i \equiv g^{ui} (mod \; p)$$
$$g^{ui}(1+g^{v-u})^i \equiv g^{ui}(mod \; p)$$
$$(1+g^{v-u})^i \equiv 1(mod \; p)$$

$w$ 共有 $gcd(i,p-1)$ 个(包括 $w$ 取 $0$ 的情况,应排除)。
注意 $x=g^u$ ,$y=g^v$ ,$1≤x≤p−1$ 、$1≤y≤m≤p−1$ ,$y$ 可有 $m$ 个,每个 $y$ 对应的 $v$ 是唯一的,因此 $v$ 也有 $m$ 个。

从 $1+g^{v-u}=g^w$ 可得 $g^{v-u}=g^w-1$ ,因此,对每个 $w$ ,$v-u$ 的值是唯一的;现在 $v$ 有 $m$ 个,每个 $v$ 对应的 $u$ 只有一个。

结论:对每个 $w$ ,数对 $(u,v)$ 共有 $m$ 个,因此数对 $(g^u,g^v)$ 共有 $m$ 对,从而数对 $(x,y)$ 共用 $m$ 对。实际的 $w$ 共有 $gcd(i,p-1)-1$ 个,因此对于确定的 $i$ ,$1≤i≤p−1$ ,$f(i)=[gcd(i,p-1)-1] \times m$

最后就是求
$$\sum^{p-1}_{i=1} if(i)(mod \; 10^9+7)=\sum^{p-1}_{i=1} i \times m \times [gcd(i,p-1)-1] (mod \; 10^9+7)$$

$$\sum^{p-1}_{i=1} if(i) = \sum^{p-1}_{i=1} i \times m \times [gcd(i,p-1)-1]=m\sum^{p-1}_{i=1} i \times gcd(i,p-1) - \frac{p(p-1)m}{2}$$

将 $1≤i≤p−1$ 中的所有 $i$ 进行分类,即 $gcd(i,p-1)$ 相同的放在一起。

设 $d=gcd(i,p-1)$ ,由于 $d=gcd(p-1-i,p-1)$ , $0≤p-1-i≤p−2$

配对

$i:1,2,3,...,p-2,p-1$

$p-1-i:p-1-1,p-1-2,...,1,0$

$$\sum^{p-1}_{i=1}i \times gcd(i,p-1)=\sum_{d|p-1} d \sum^{p-1}_{i=1,d|i} i \times [gcd(i,p-1)=d]$$

$$=\sum_{d|p-1} d \sum^{p-1}_{i=1,d|i} i \times [gcd(\frac{i}{d},\frac{p-1}{d})=1]$$

对 $d|i$ ,记 $i=d_j$ ,则 $j=1,2,..., \frac{p-1}{d}$ ,代入上述等式最后一个公式,并重新将 $j$ 换回到 $i$ ,则有

$$\sum_{d|p-1} d \sum^{p-1}_{i=1} i \times [gcd( \frac{i}{d} , \frac{p-1}{d}) = 1]=\sum_{d|p-1} d^2 \sum^{ \frac{p-1}{d}}_{i=1} i \times [gcd(i , \frac{p-1}{d}) = 1]$$

$$=\sum_{d|p-1}d^2\frac{\frac{p-1}{d} \varphi (\frac{p-1}{d})+[\frac{p-1}{d}=1]}{2}$$

:

  • 当z>1时
    $$\sum_{i=1}^z i \times [gcd(i,z)=1]$$

$$=\frac{1}{2}(\sum_{i=1}^z i \times [gcd(i,z)=1]+\sum_{i=1}^z i \times [gcd(z-i,z)=1])$$
$$=\frac{1}{2}(\sum_{i=1}^z i \times [gcd(i,z)=1]+\sum_{i=1}^z (z-i) \times [gcd(z-i,z)=1])$$
$$=\frac{1}{2}\sum_{i=1}^z(i+(z-i)) \times [gcd(i,z)=1]=\frac{1}{2}\sum_{i=1}^z z \times [gcd(i,z)=1]$$
$$=\frac{1}{2}z\sum_{i=1}^z[gcd(i,z)=1]=\frac{1}{2}z \varphi(z)$$

  • 当z=1时
    $$\sum_{i=1}^z i \times [gcd(i,z)=1]=1=\frac{z \varphi(z) + 1}{2}$$

代码

#include<bits/stdc++.h>
const int mod = 1e9+7;
using namespace std;
typedef long long ll;

int mod_mul(int a,int b)
{
    ll c = 1LL * a * b;
    return c - c / mod * mod;
}

int euler(int n) 
{
    int ret = n;
    int i;
    for(i = 2 ; i * i <= n ; i ++)
    {
        if(n % i == 0)
        {
            ret = ret - ret / i;
            while(n % i == 0)
            {
                n /= i;
            }
        }
    }
    if(n > 1)
    {
        ret = ret - ret / n;
    }
    return ret;
}

int solve(int n)
{
    int ans = 0;
    int tmp = 0;
    for(int i = 1 , j ; i * i <= n; i++)
    {
        j = n / i;
        if(i * j == n)
        {
            tmp = mod_mul( (1LL * j * euler(j) + ( j == 1 ) ) / 2 % mod, mod_mul( i , i ) );
            if((ans += tmp) >= mod) ans -= mod;


            if(i != j)
            {
                tmp = mod_mul( (1LL * i * euler(i) + ( i == 1 ) ) / 2 % mod, mod_mul( j , j ) );
                if((ans += tmp) >= mod) ans -= mod;
            }

        }
    }
    ans -= mod_mul( mod_mul( n, n + 1), 500000004);
    if(ans < 0) ans += mod;
    return ans;
}
int main()
{
    int t;
    int m,p,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        cas++;
        scanf("%d%d",&m,&p);
        int ans = mod_mul( solve(p - 1), m );
        printf("Case #%d: ",cas);
        printf("%d\n",ans);
    }
    return 0;
}
本文作者:Author:     文章标题:原根计算及应用
本文地址:https://alphalrx.cn/index.php/archives/55/     
版权说明:若无注明,本文皆为“LRX's Blog”原创,转载请保留文章出处。
Last modification:November 2nd, 2019 at 02:47 pm
给作者赏一杯奶茶吧!

Leave a Comment