Primitive root of a prime number n modulo n | Java 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
import java . util . * ; class GFG { static boolean 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 ; } static int power ( int x , int y , int p ) { while ( y > 0 ) { if ( y % 2 == 1 ) { res = ( res * x ) % p ; } x = ( x * x ) % p ; } return res ; } static void findPrimefactors ( HashSet < Integer > s , int n ) { while ( n % 2 == 0 ) { s . add ( 2 ) ; n = n / 2 ; } for ( int i = 3 ; i <= Math . sqrt ( n ) ; i = i + 2 ) { while ( n % i == 0 ) { s . add ( i ) ; n = n / i ; } } if ( n > 2 ) { s . add ( n ) ; } } static int findPrimitive ( int n ) { HashSet < Integer > s = new HashSet < Integer > ( ) ; if ( isPrime ( n ) == false ) { return - 1 ; } int phi = n - 1 ; findPrimefactors ( s , phi ) ; for ( int r = 2 ; r <= phi ; r ++ ) { boolean flag = false ; for ( Integer a : s ) { if ( power ( r , phi / ( a ) , n ) == 1 ) { flag = true ; break ; } } if ( flag == false ) { return r ; } } return - 1 ; } public static void main ( String [ ] args ) { int n = 761 ; System . out . println ( " ▁ Smallest ▁ primitive ▁ root ▁ of ▁ " + n + " ▁ is ▁ " + findPrimitive ( n ) ) ; } }