能力值：
![]()
(RANK：1060 )
|
-
-
2 楼
http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots
|
能力值：
( LV2，RANK：10 )
|
-
-
3 楼
设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-1所有的不同质因子 是不是指小于x-1的所有的素数
a^(x-1)/p1 (mod p) 这里a^(x-1)/p1不知道怎么分解
|
能力值：
( LV2，RANK：10 )
|
-
-
4 楼
比如说，p=13,a=2
则p-1=12=2^2*3
计算
2^(12/2)=2^6=12mod13
2^(12/3)=2^4=3mod13
均不等于1，所以a是原根。
|
能力值：
( LV2，RANK：10 )
|
-
-
5 楼
2^(12/5)=2^6=12mod13 呢
12/5=2？ 还是要拆开来计算
|
能力值：
( LV2，RANK：10 )
|
-
-
6 楼
呃，为什么要计算12/5呢……
仔细看看，想想为什么我要将p-1写成分解的形式吧。
|
|
|
|
