Discrete logarithm ( Find an integer k such that a ^ k is congruent modulo b ) | Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; $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 ; Function to calculate k for given a , b , m ; Store all values of a ^ ( n * i ) of LHS ; Calculate ( a ^ j ) * b and check for collision ; If collision occurs i . e . , LHS = RHS ; Check whether ans lies below m or not ; Driver code
< ? php function powmod ( $ x , $ y , $ p ) { while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function discreteLogarithm ( $ a , $ b , $ m ) { $ n = ( int ) sqrt ( $ m ) + 1 ; $ value = array_fill ( 0 , $ m , NULL ) ; for ( $ i = $ n ; $ i >= 1 ; -- $ i ) $ value [ powmod ( $ a , $ i * $ n , $ m ) ] = $ i ; for ( $ j = 0 ; $ j < $ n ; ++ $ j ) { $ cur = ( powmod ( $ a , $ j , $ m ) * $ b ) % $ m ; if ( $ value [ $ cur ] ) { $ ans = $ value [ $ cur ] * $ n - $ j ; if ( $ ans < $ m ) return $ ans ; } } return -1 ; } $ a = 2 ; $ b = 3 ; $ m = 5 ; echo discreteLogarithm ( $ a , $ b , $ m ) , " " ; $ a = 3 ; $ b = 7 ; $ m = 11 ; echo discreteLogarithm ( $ a , $ b , $ m ) , " " ; ? >