# exponentielle modulaire rapide

A=int(input("entrez A:"))
B=int(input("entrez B:"))
N=int(input("entrez N:"))

# calcul de la représentation binaire b de B
b=[B%2]
C=B//2
while C>=1:
    b+=[C%2]
    C=C//2
print("représentation binaire de b:",b)

# création de la liste avec les puissances successives de A (mod N): A, A^2, A^4, A^8...
L=[A%N]
for i in range(len(b)-1):
    L+=[(L[i]**2)%N]
print("puissances successives de A:",L)

# calcul de l'exponentielle modulaire (ne prenant en compte que les termes avec b[i]=1)
S=1
for i in range(len(b)):
    if b[i]:
        S=(S*L[i])%N
print("A^B(mod N) =",S)

# vérification avec la fonction Python pow(A,B,N)
print("pow(A,B,N) =",pow(A,B,N))