Pour certains calculs portant sur les calculs de puissance (x**y) et de puissance modulaire (x**y%z) des nombres entiers longs, on est quelquefois obligé de les programmer, et le calcul direct est beaucoup trop long: on va donner ici une méthode plus rapide.

Ce n'est cependant pas utile dans les dernières versions de Python: la fonction pow(x,y) et pow(x,y,z) font ça très bien, et plus rapidement.

Référence pour l'exponentiation modulaire (entre autres):

http://www.labri.fr/perso/betrema/deug/poly/exp-rapide.html

Référence pour l'exponentiation modulaire (entre autres):

http://fr.wikipedia.org/wiki/Exponentiation_modulaire

Code proposé:

def lpow(x,y):
    """Calcul rapide de la puissance entière avec x et y entiers """
    result = 1
    while y != 0:
        if y&1 == 1:  # si y impair
            result *= x
            y -= 1
        else:  #  y est pair
            x *= x
            y >>= 1
    return result

def lpowmod(x, y, n):
    """puissance modulaire: (x**y)%n avec x, y et n entiers"""
    result = 1
    while y>0:
        if y&1>0:
            result = (result*x)%n
        y >>= 1
        x = (x*x)%n    
    return result