Multiplicative order | Java program to implement multiplicative order ; function for GCD ; Function return smallest + ve integer that holds condition A ^ k ( mod N ) = 1 ; result store power of A that rised to the power N - 1 ; modular arithmetic ; return smallest + ve integer ; increment power ; driver program to test above function
import java . io . * ; class GFG { static int GCD ( int a , int b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } static int multiplicativeOrder ( int A , int N ) { if ( GCD ( A , N ) != 1 ) return - 1 ; int result = 1 ; int K = 1 ; while ( K < N ) { result = ( result * A ) % N ; if ( result == 1 ) return K ; K ++ ; } return - 1 ; } public static void main ( String args [ ] ) { int A = 4 , N = 7 ; System . out . println ( multiplicativeOrder ( A , N ) ) ; } }