Discrete logarithm ( Find an integer k such that a ^ k is congruent modulo b ) | Python3 program to calculate discrete logarithm ; 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
import math ; NEW_LINE def powmod ( x , y , p ) : NEW_LINE INDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p ; NEW_LINE DEDENT x = ( x * x ) % p ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def discreteLogarithm ( a , b , m ) : NEW_LINE INDENT n = int ( math . sqrt ( m ) + 1 ) ; NEW_LINE value = [ 0 ] * m ; NEW_LINE for i in range ( n , 0 , - 1 ) : NEW_LINE INDENT value [ powmod ( a , i * n , m ) ] = i ; NEW_LINE DEDENT for j in range ( n ) : NEW_LINE INDENT cur = ( powmod ( a , j , m ) * b ) % m ; NEW_LINE if ( value [ cur ] ) : NEW_LINE INDENT ans = value [ cur ] * n - j ; NEW_LINE if ( ans < m ) : NEW_LINE INDENT return ans ; NEW_LINE DEDENT DEDENT DEDENT return - 1 ; NEW_LINE DEDENT a = 2 ; NEW_LINE b = 3 ; NEW_LINE m = 5 ; NEW_LINE print ( discreteLogarithm ( a , b , m ) ) ; NEW_LINE a = 3 ; NEW_LINE b = 7 ; NEW_LINE m = 11 ; NEW_LINE print ( discreteLogarithm ( a , b , m ) ) ; NEW_LINE