Primitive root of a prime number n modulo n | C ++ 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 point . 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPrime ( int n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return true ; if ( n % 2 == 0 n % 3 == 0 ) return false ; for ( int i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return false ; return true ; } int power ( int x , unsigned int y , int p ) { while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } void findPrimefactors ( unordered_set < int > & s , int n ) { while ( n % 2 == 0 ) { s . insert ( 2 ) ; n = n / 2 ; } for ( int i = 3 ; i <= sqrt ( n ) ; i = i + 2 ) { while ( n % i == 0 ) { s . insert ( i ) ; n = n / i ; } } if ( n > 2 ) s . insert ( n ) ; } int findPrimitive ( int n ) { unordered_set < int > s ; if ( isPrime ( n ) == false ) return -1 ; int phi = n - 1 ; findPrimefactors ( s , phi ) ; for ( int r = 2 ; r <= phi ; r ++ ) { bool flag = false ; for ( auto it = s . begin ( ) ; it != s . end ( ) ; it ++ ) { if ( power ( r , phi / ( * it ) , n ) == 1 ) { flag = true ; break ; } } if ( flag == false ) return r ; } return -1 ; } int main ( ) { int n = 761 ; cout << " ▁ Smallest ▁ primitive ▁ root ▁ of ▁ " << n << " ▁ is ▁ " << findPrimitive ( n ) ; return 0 ; }