Exponential Squaring ( Fast Modulo Multiplication ) | prime modulo value ; for cases where exponent is not an even value ; Driver Code
N = 1000000007 ; NEW_LINE def exponentiation ( bas , exp ) : NEW_LINE INDENT t = 1 ; NEW_LINE while ( exp > 0 ) : NEW_LINE INDENT if ( exp % 2 != 0 ) : NEW_LINE INDENT t = ( t * bas ) % N ; NEW_LINE DEDENT bas = ( bas * bas ) % N ; NEW_LINE exp = int ( exp / 2 ) ; NEW_LINE DEDENT return t % N ; NEW_LINE DEDENT bas = 5 ; NEW_LINE exp = 100000 ; NEW_LINE modulo = exponentiation ( bas , exp ) ; NEW_LINE print ( modulo ) ; NEW_LINE