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 Code
< ? php function GCD ( $ a , $ b ) { if ( $ b == 0 ) return $ a ; return GCD ( $ b , $ a % $ b ) ; } function multiplicativeOrder ( $ A , $ N ) { if ( GCD ( $ A , $ N ) != 1 ) return -1 ; $ result = 1 ; $ K = 1 ; while ( $ K < $ N ) { $ result = ( $ result * $ A ) % $ N ; if ( $ result == 1 ) return $ K ; $ K ++ ; } return -1 ; } $ A = 4 ; $ N = 7 ; echo ( multiplicativeOrder ( $ A , $ N ) ) ; ? >