Multiplicative order | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int GCD ( int a , int b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } int multiplicativeOrder ( int A , int N ) { if ( GCD ( A , N ) != 1 ) return -1 ; unsigned int result = 1 ; int K = 1 ; while ( K < N ) { result = ( result * A ) % N ; if ( result == 1 ) return K ; K ++ ; } return -1 ; } int main ( ) { int A = 4 , N = 7 ; cout << multiplicativeOrder ( A , N ) ; return 0 ; }