201605171607.txt.md

#! /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'