Discrete logarithm ( Find an integer k such that a ^ k is congruent modulo b ) | PHP program to calculate discrete logarithm ; Calculate a ^ n ; Store all values of a ^ ( n * i ) of LHS ; Calculate ( a ^ j ) * b and check for collision ; Driver code
< ? php function discreteLogarithm ( $ a , $ b , $ m ) { $ n = ( int ) sqrt ( $ m ) + 1 ; $ an = 1 ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) $ an = ( $ an * $ a ) % $ m ; $ value = array_fill ( 0 , $ m , NULL ) ; for ( $ i = 1 , $ cur = $ an ; $ i <= $ n ; ++ $ i ) { if ( ! $ value [ $ cur ] ) $ value [ $ cur ] = $ i ; $ cur = ( $ cur * $ an ) % $ m ; } for ( $ i = 0 , $ cur = $ b ; $ i <= $ n ; ++ $ i ) { if ( $ value [ $ cur ] ) { $ ans = $ value [ $ cur ] * $ n - $ i ; if ( $ ans < $ m ) return $ ans ; } $ cur = ( $ cur * $ a ) % $ m ; } return -1 ; } $ a = 2 ; $ b = 3 ; $ m = 5 ; echo discreteLogarithm ( $ a , $ b , $ m ) , " " ; $ a = 3 ; $ b = 7 ; $ m = 11 ; echo discreteLogarithm ( $ a , $ b , $ m ) ; ? >