【转】原根

转自：http://blog.csdn.net/acdreamers/article/details/8883285

原根

定义：设，，使得成立的最小的，称为对模的阶，记为。

定理：如果模有原根，那么它一共有个原根。

定理：若，，，则。

定理：如果为素数，那么素数一定存在原根，并且模的原根的个数为。

定理：设是正整数，是整数，若模的阶等于，则称为模的一个原根。

假设一个数对于模来说是原根，那么的结果两两不同,且有，那么可以称为是模的一个原根，归根到底就是当且仅当指数为的时候成立。（这里是素数）

模有原根的充要条件：，其中是奇素数。

求模素数原根的方法：对素因子分解，即是的标准分解式，若恒有

成立，则就是的原根。（对于合数求原根，只需把换成即可）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 using namespace std;
 5 int prime[100000];
 6 void getprime(int p)
 7 {
 8     prime[0]=0;
 9     int i;
10     int tmp=p;
11     for(i=2;i<=sqrt(p);i++)
12     {
13         if(tmp%i==0)
14         {
15             prime[++prime[0]]=i;
16             while(tmp%i==0)
17                 tmp/=i;
18         }
19     }
20 }
21 
22 int pown(int a,int n,int m)
23 {
24     long long re=1;
25     int i;
26     long long tmp=a;
27     if(n&1)
28         re*=tmp;
29     n>>=1;
30     while(n)
31     {
32         tmp=tmp*tmp%m;
33         if(n&1)
34             re=re*tmp%m;
35         n>>=1;
36     }
37     return re;
38 }
39 
40 int getyuangen(int p)
41 {
42     int i,j;
43     getprime(p-1);
44     bool flag;
45     for(i=2;i<p;i++)
46     {
47         flag=true;
48         for(j=1;j<=prime[0];j++)
49         {
50             if(pown(i,(p-1)/prime[j],p)==1)
51             {
52                 flag=false;
53                 break;
54             }
55         }
56         if(flag)
57             return i;
58     }
59     return 0;
60 }
61 int main()
62 {
63 
64     int p;
65     scanf("%d",&p);
66     printf("%d
",getyuangen(p));
67     return 0;
68 }

View Code