关于原根的算法

On the Algorithm for Primitive Root

本文给出了求模p~α和2p~α的一个或全部原根的切实可行的办法,比经典求法简便很多,从而可节省大量的时间和精力。

In this paper we have intended, among others to prove the following: Theorem 1 Let p=4n+1 be prime, and let g be a primitive root modulo p, then g^(λ_1),g^(λ_2),…,g^(λ_k),k=1/4φ(p-1),1=λ_1<λ_2<λ…,λ_k<(p-1)/4, (λ_i, p-1)=1 and (g^(λ_i))^(-1), p-g^(λ_i), p-(g^(λ_i))^-1, i=1,2,…,k are all primitive roots modulo p. heorem 4' Let g_i, i=1,2,…,φ(p-1) be totality of primitive roots modulo p, then the totality of primitive roots modulo p^2 is exactly egual to the g_i+jp,i=1,2,…,φ(p-1),j=0,1,2,…,p-1 which are not equal f_i=g_i^p(mod p^2), 0<f_i<p^2