# -*- coding: utf-8 -*-
"""


@author: V. Le Prince
"""
    
    
    
#PGCD
def pgcd(a,b):
    """ a et b deux entiers naturels non tous deux nuls"""
    r1,r2=a,b
    while r2!=0:
        r1,r2=r2,r1%r2
    return r1


def pgcdRec(a,b):
    """ a et b deux entiers naturels non tous deux nuls"""
    if b ==0 :
        return a
    else :
        return pgcdRec(b,a%b)
    
print(pgcdRec(117,25))
print(pgcdRec(0,25))
print(pgcdRec(115,25))
    
# Euclide \'etendu
def Bezout(a,b):
    r1,r2=a,b
    u1,v1=1,0
    u2,v2=0,1
    #Invariant : a*ui+ b*vi = ri pour i = 1,2
    while r2!=0:
        q=r1//r2
        r=r1%r2
        u,v=u2,v2
        u2,v2=u1-q*u2,v1-q*v2
        u1,v1=u,v
        r1,r2=r2,r
    return [u1,v1] 
    
#test 
print(Bezout(117,25))    

        
    
#Indicatrice d'Euler par une m\'ethode de crible
#Peut facilement \^etre adapt\'e pour conna\^itre la liste 
    # des \'el\'ements inversibles de Z/nZ
def phi(n):
    L=n*[1]
    L[0] = 0
    phi=1
    i=2
    while i<n:
        if L[i]!=0:
            if pgcd(i,n)==1:
                phi=phi+1
            else :
                j=i
                while j<n:
                    L[j]=0
                    j=j+i
        i=i+1
    return phi   

print(phi(418))
     
# Inversion modulaire dans Z/nZ
def Inv_mod(x,n):
    assert pgcd(x,n)==1 , " x doit être premier avec n"
    u=Bezout(x,n)[0]
    return u%n

print(Inv_mod(14,97))
print(Inv_mod(14,98))

#Théorème chinois 
def resout(a,n,b,m):
    assert pgcd(n,m)==1 , " n et m doivent être premiers entre eux"
    u,v =Bezout(n,m) #u*n+v*m=1
    return (a*v*m+b*u*n)%(n*m)

#RSA  
p , q = 127 , 131           
n=p*q
phi_n = 126 * 130
e=17
d = Inv_mod(e,phi_n)



def puis(x,k,n):#calcule x**k [n]
    res=1
    for i in range(k):
        res=(res*x)%n
    return res

def codeRSA(m,n,e):
    return puis(m,e,n)


def decodeRSA(x,n,d):
    return puis(x,d,n)


#message à transmettre       
m = 2222

m_code = codeRSA(m,n,e)
print(m_code)
    

m_code_decode = decodeRSA(m_code,n,d) 
print(m_code_decode)