Hensel 's Lemma | Function to find the modular inverse of a modulo m ; Apply the Euclidean algorithm , to find the modular inverse ; Function to find the derivative of f ( x ) and f '(x) = 3 * (x ^ 2) ; Function to find the image of x in f ( x ) = x ^ 3 - k . ; Function to find the next power of the number ; Next power of prime for which solution is to be found ; Using Hensel 's recursion to  find the solution(next_a) for  next power of prime ; If next_a < 0 return equivalent positive remainder modulo p ; Return the next power of a ; Function to find the solution of the required exponent of prime ; The lemma does not work for derivative of f ( x ) at a1 ; Looping from 1 to power of prime whose solution is to be found ; Final answer after evaluating all the exponents up till the required exponent ; Driver Code ; Function Call
def inv ( a , m ) : NEW_LINE INDENT m0 = m NEW_LINE x0 = 0 NEW_LINE x1 = 1 NEW_LINE if ( m == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( a > 1 ) : NEW_LINE INDENT q = a // m NEW_LINE t = m NEW_LINE m = a % m NEW_LINE a = t NEW_LINE t = x0 NEW_LINE x0 = x1 - q * x0 NEW_LINE x1 = t NEW_LINE DEDENT if ( x1 < 0 ) : NEW_LINE INDENT x1 += m0 NEW_LINE DEDENT return x1 NEW_LINE DEDENT def derivative ( x ) : NEW_LINE INDENT return 3 * x * x NEW_LINE DEDENT def Image ( x , k ) : NEW_LINE INDENT return x * x * x - k NEW_LINE DEDENT def next_power ( a_t , t , a1 , prime , k ) : NEW_LINE INDENT power_p = int ( pow ( prime , t + 1 ) ) NEW_LINE next_a = ( a_t - Image ( a_t , k ) * inv ( derivative ( a1 ) , prime ) ) % power_p NEW_LINE if ( next_a < 0 ) : NEW_LINE INDENT next_a += power_p NEW_LINE return next_a NEW_LINE DEDENT return next_a NEW_LINE DEDENT def powerOfPrime ( prime , power , k , a1 ) : NEW_LINE INDENT if ( derivative ( a1 ) != 0 ) : NEW_LINE INDENT a_t = a1 NEW_LINE for p in range ( 1 , power ) : NEW_LINE INDENT a_t = next_power ( a_t , p , a1 , prime , k ) NEW_LINE DEDENT return a_t NEW_LINE DEDENT return - 1 NEW_LINE DEDENT prime = 7 NEW_LINE a1 = 3 NEW_LINE power = 2 NEW_LINE k = 3 NEW_LINE print ( powerOfPrime ( prime , power , k , a1 ) ) NEW_LINE