Primitive root of a prime number n modulo n | Python3 program to find primitive root of a given number n ; Returns True if n is prime ; Corner cases ; This is checked so that we can skip middle five numbers in below loop ; Iterative Function to calculate ( x ^ n ) % p in O ( logy ) ; x = x % p Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 y = y / 2 ; Utility function to store prime factors of a number ; Print the number of 2 s that divide n ; n must be odd at this po . So we can skip one element ( Note i = i + 2 ) ; While i divides n , print i and divide n ; This condition is to handle the case when n is a prime number greater than 2 ; Function to find smallest primitive root of n ; Check if n is prime or not ; Find value of Euler Totient function of n . Since n is a prime number , the value of Euler Totient function is n - 1 as there are n - 1 relatively prime numbers . ; Find prime factors of phi and store in a set ; Check for every number from 2 to phi ; Iterate through all prime factors of phi . and check if we found a power with value 1 ; Check if r ^ ( ( phi ) / primefactors ) mod n is 1 or not ; If there was no power with value 1. ; If no primitive root found ; Driver Code
from math import sqrt NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i = 5 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i = i + 6 NEW_LINE DEDENT return True NEW_LINE DEDENT def power ( x , y , p ) : NEW_LINE INDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def findPrimefactors ( s , n ) : NEW_LINE INDENT while ( n % 2 == 0 ) : NEW_LINE INDENT s . add ( 2 ) NEW_LINE n = n // 2 NEW_LINE DEDENT for i in range ( 3 , int ( sqrt ( n ) ) , 2 ) : NEW_LINE INDENT while ( n % i == 0 ) : NEW_LINE INDENT s . add ( i ) NEW_LINE n = n // i NEW_LINE DEDENT DEDENT if ( n > 2 ) : NEW_LINE INDENT s . add ( n ) NEW_LINE DEDENT DEDENT def findPrimitive ( n ) : NEW_LINE INDENT s = set ( ) NEW_LINE if ( isPrime ( n ) == False ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT phi = n - 1 NEW_LINE findPrimefactors ( s , phi ) NEW_LINE for r in range ( 2 , phi + 1 ) : NEW_LINE INDENT flag = False NEW_LINE for it in s : NEW_LINE INDENT if ( power ( r , phi // it , n ) == 1 ) : NEW_LINE INDENT flag = True NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag == False ) : NEW_LINE INDENT return r NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT n = 761 NEW_LINE print ( " Smallest ▁ primitive ▁ root ▁ of " , n , " is " , findPrimitive ( n ) ) NEW_LINE