#! /usr/bin/env python

-- coding: cp936 --

Copyleft (c) 2016, 2026

------------------------------------------------------------------------

Author : scz cloudsky@gmail.com

Create : 2016-05-17 16:07

Modify :

------------------------------------------------------------------------

The only thing they can't take from us are our minds. !H

寻找指定数字的所有原根，不要求n是素数。

./primitive_root_finder.py 41

./primitive_root_finder.py 487

./primitive_root_finder.py 237169 1

import sys, signal

def gcd ( a, b ) : while b != 0 : ( a, b ) = ( b, a % b ) return( a )

end of gcd

def totient ( n ) : ret = [] x = 1 while x < n : if 1 == gcd( x, n ) : ret.append( x ) x += 1 return( ret )

end of totient

def phi ( n ) : ret = 0 x = 1 while x < n : if 1 == gcd( x, n ) : ret += 1 x += 1 return( ret )

end of phi

def get_factor ( n ) : ret = [1] x = 2 y = n // 2 while x <= y : if 0 == n % x : ret.append( x ) x += 1 ret.append( n ) return( ret )

end of get_factor

def have_primitive_root ( n ) : ret = False if 2 == n or 4 == n : ret = True else : if 0 == n % 2 : n = n // 2 if 0 != n % 2 : p = 3 c = 1 op = 0 while n >= p*p : if 0 == n % p : n = n // p if op > 0 and p != op : c += 1 break op = p else : p = p + 1 # # end of while # if 1 == c and n > 1 : if op > 0 and n != op : c += 1 if 1 == c : ret = True return( ret )

end of have_primitive_root

if 'main' == name : try : signal.signal( signal.SIGINT, signal.SIG_DFL ) if len( sys.argv ) > 2 : verbose = True else : verbose = False n = int( sys.argv[1], 0 ) if have_primitive_root( n ) : candidate = totient( n ) phin = len( candidate ) phiphin = phi( phin ) phin_factor = get_factor( phin ) ret = [] for g in candidate : for x in phin_factor : if 1 == pow( g, x, n ) : if x == phin : if verbose : print g ret.append( g ) break if len( ret ) == phiphin : break # # end of for # print ret else : print '%d have not primitive root' % n except KeyboardInterrupt : print '\nCtrl-C'