Discrete logarithm ( Find an integer k such that a ^ k is congruent modulo b ) | Python3 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
import math ; NEW_LINE def discreteLogarithm ( a , b , m ) : NEW_LINE INDENT n = int ( math . sqrt ( m ) + 1 ) ; NEW_LINE an = 1 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT an = ( an * a ) % m ; NEW_LINE DEDENT value = [ 0 ] * m ; NEW_LINE cur = an ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( value [ cur ] == 0 ) : NEW_LINE INDENT value [ cur ] = i ; NEW_LINE DEDENT cur = ( cur * an ) % m ; NEW_LINE DEDENT cur = b ; NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT if ( value [ cur ] > 0 ) : NEW_LINE INDENT ans = value [ cur ] * n - i ; NEW_LINE if ( ans < m ) : NEW_LINE INDENT return ans ; NEW_LINE DEDENT DEDENT cur = ( cur * a ) % m ; NEW_LINE 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