设 g是mod p意义下的一个原根.则 g^(p-1)=1 mod p 且对于 k=1,2...p-2:g^k不=1 mod p 接下来,当p不整除x时：可设x=g^y mod p 原方程化为 by=y mod (p-1) (y=1,2...p-1) 即 (b-1)y=0 mod (p-1) 即 (b-1)/gcd(b-1,p-1)...