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
def GCD ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return GCD ( b , a % b ) NEW_LINE DEDENT def multiplicativeOrder ( A , N ) : NEW_LINE INDENT if ( GCD ( A , N ) != 1 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT result = 1 NEW_LINE K = 1 NEW_LINE while ( K < N ) : NEW_LINE INDENT result = ( result * A ) % N NEW_LINE if ( result == 1 ) : NEW_LINE INDENT return K NEW_LINE DEDENT K = K + 1 NEW_LINE DEDENT return - 1 NEW_LINE DEDENT A = 4 NEW_LINE N = 7 NEW_LINE print ( multiplicativeOrder ( A , N ) ) NEW_LINE