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 ) ; Initialize result ; 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
function powmod ( x , y , p ) { let res = 1 ; x = x % p ; while ( y > 0 ) { if ( ( y & 1 ) > 0 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } function discreteLogarithm ( a , b , m ) { let n = ( parseInt ( Math . sqrt ( m ) , 10 ) + 1 ) ; let value = new Array ( m ) ; value . fill ( 0 ) ; for ( let i = n ; i >= 1 ; -- i ) value [ powmod ( a , i * n , m ) ] = i ; for ( let j = 0 ; j < n ; ++ j ) { let cur = ( powmod ( a , j , m ) * b ) % m ; if ( value [ cur ] > 0 ) { let ans = value [ cur ] * n - j ; if ( ans < m ) return ans ; } } return - 1 ; } let a = 2 , b = 3 , m = 5 ; document . write ( discreteLogarithm ( a , b , m ) + " " ) ; a = 3 ; b = 7 ; m = 11 ; document . write ( discreteLogarithm ( a , b , m ) + " " ) ;