3731.sagews

Le TP d'aujourd'hui portera sur l'arithmétique. On va notamment faire des calculs sur Z/nZ. De même que la semaine dernière il ne fallait pas confondre l'objet mathématique (ensemble) et sa représentation informatique (liste), il faudra prendre garde cette semaine que les entiers peuvent réprésenter un entier mathématique ou bien un élément de Z/nZ (une classe), suivant le contexte.

Si par exemple n=5 et qu'on veut tester l'égalité entre 2 et 7, écrire 2==7 peut être la réponse... ou pas.

Exercice 1 : Écrivez une fonction DivEucl(a,b) qui renvoie le quotient et le reste de la division euclidienne de a par b (entiers), en n'utilisant que la soustraction (avec if, for et while, bien sûr).

def DivEucl(a,b):
    q = 0
    r = a
    while r>=b:
        q+=1
        r-=b
    return (q,r)

Exercice 2 : Programmez l'algorithme d'Euclide en utilisant l'exercice 1. On rappelle que l'algorithme se déroule de la manière suivante :

- On divise a par b, obtenant q et r ;

- on divise b par r, obtenant q' et r'

- et ainsi de suite. Le résultat renvoyé correspond au dernier reste non nul.

Euclide(26,39)

13

Exercice 3 : Grâce à l'exercice 1, écrivez une fonction qui à un entier associe l'élément de sa classe compris entre 0 et n-1. Puis, écrivez des fonctions qui testent l'égalité et qui effectuent l'addition et la multiplication dans Z/nZ.

def Classe(a,n):
    q,r = DivEucl(a,n)
    return r                                 # En fait, on peut aussi écrire a%n, mais je voulais utiliser l'exercice 1.
    
def Egalite(a,b,n):
    return (a%n == b%n)

def Addition (a,b,n):
    return (a+b)%n
    
def Multiplication (a,b,n):
    return (a*b)%n

En déduire une fonction Divise(a,b,n) qui teste si a divise b dans Z/nZ (il existe k tel que ka=b).

def Divise (a,b,n):
    for k in range(n):
        if Egalite(k*a,b,n): return True
    return False

Vous avez appris qu'un élément de Z/nZ est soit inversible (i.e. diviseur de 1), soit diviseur de zéro. En vous inspirant de la question précédente, écrivez une fonction Diviseur(a,n) qui indique dans quel cas on est et qui renvoie un élément k de Z/nZ tel que ka = 0 ou 1, suivant le cas (k non nul, bien sur).

def Inversible (a,n):
    for k in range(1,n):
        if k*a%n==1: 
            return (1,k)
        elif k*a%n==0: 
            return (0,k)
    print "Les mathématiques sont incohérentes"

Exercice 4 : On va représenter un polynôme de degré 3  aX³+bX²+cX+d comme un tuple (a,b,c,d). Écrivez une fonction Polynul(a,b,c,d,n) qui teste si aX³+bX²+cX+d = 0 pour toute valeur de X (dans Z/nZ). 

def Polynul(a,b,c,d,n):
    for X in range(n):
        if a*X**3+b*X**2+c*X+d%n!=0: return False
    return True

Exercice 5 : Écrivez une fonction CribleErathostène(n) qui construit une liste allant de 2 à n, puis ne laisse que les nombre premiers. Pour cela :

- Prendre les éléments de la liste un par un ;

- Supprimer tous ses multiples de la liste (sauf lui-même !) ;

- Prendre l'élément suivant, et ainsi de suite.

Vous aurez sans doute besoin de [0]*n qui construit une liste de taille n remplie de 0. Pour faire une boucle for qui fait des sauts, consultez l'aide de "range" (avec "range?"). Rappelez-vous le TD précédent : quand peut-on s'arrêter ?

def Eratosthene(n):                                    # Idée générale : pour 'supprimer' un nombre, on le remplace par 0.
    liste = [0]*(n-1)
    for i in range(n-1): liste[i]=i+2                  # L'entier i est stocké dans la cellule i-2
    
    for k in range(sqrt(n)):
        if liste[k]!=0:                                # Il n'a pas été supprimé : c'est donc k+2
            for j in range(2*k+2,n-1,k+2):             # On commence à 2(k+2) (stocké en 2k+2) pour ne pas effacer le premier.
                liste[j]=0                             # Et on progresse par sauts de k+2
                
    reponse=[]
    for k in liste:                                    # Maintenant on construit la reponse en supprimant les 0
        if k!=0: reponse.append(k)
    return reponse
    
Eratosthene(54)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]

Exercice 6 : Écrire une fonction Factorisation(n) qui factorise un entier n en facteurs premiers. Utilisez la question précédente et demandez-vous comment vous feriez à la main (on ne cherche pas à être efficace). Renvoyez le résultat sous la forme que vous préférez, par exemple une liste de couples (facteur, multiplicité), i.e. 40 = 2³.5 -> [(2,3),(5,1)].

def Factorisation(n):
    def add_list(a,l):
        fait = False
        for k in range (len(l)):
            (x,y) = l[k]
            if a==x: 
                l[k] = (x,y+1)
                fait = True
        if not fait: l.append((a,1))
    
    nombre = n
    reponse = []
    liste = Eratosthene(n)
    k=0
    while nombre!=1 :
        if nombre%liste[k] == 0:
            add_list(liste[k],reponse)
            nombre = nombre//liste[k]
        elif liste[k]>=sqrt(nombre) :
            add_list(nombre, reponse)
            nombre=1
        else:     
            k=k+1
    return reponse

Exercice 7: Calculons le pgcd d'une deuxième façon ! Grâce à l'exercice précédent, écrivez une fonction pgcd(a,b) qui renvoie le pgcd de a et b en regardant leurs facteurs premiers communs. Comparez le résultat avec Euclide(a,b).

def pgcd(a,b):
    deca, decb = Factorisation(a),Factorisation(b)
    pgcd = []
    k1, k2 = 0,0
    while k1<len(deca) and k2<len(decb):
        (x,y) = deca[k1]
        (x2,y2) = decb[k2]
        if x==x2 : 
            pgcd.append((x, min(y,y2)))
            k1 +=1
            k2 +=1
        elif x<x2: k1+=1
        else : k2+=1
    return pgcd

def evaluate (l):
    if l==[]: return 1
    else: 
        (x,y) = l[0]
        return x**y*evaluate (l[1:])

Exercice 8 : Écrivez une fonction IndicatriceEuler(n) qui renvoie φ(n), c'est-à-dire le nombre d'éléments inversibles de Z/nZ. Utilisez la dernière question de l'exercice 3.

def IndicatriceEuler(n):
    phi = 0
    for i in range(n):
        (x,y) = Inversible(i,n)
        if x==1: phi+=1
    return phi
        
IndicatriceEuler(7)

6

Exercice bonus (*) : Écrivez une fonction Reste(a,b,n) qui prend en entrée un entier a, un entier b (très grand) et un entier n>1, et qui calcule le reste de a^b  modulo n, le plus vite possible. Notamment, éviter de multiplier par a b fois. Indice : observer la périodicité et utiliser la division euclidienne.

def Reste(a,b,n):
    reste = a%n
    puissance = 1
    table = [0]*n
    while table[reste]==0:
        table[reste]=puissance
        reste = reste*a%n
        puissance +=1
    preperiode = table[reste]
    periode = puissance-table[reste]
    (q,r) = DivEucl(b-preperiode, periode)
    return (reste*(a**r))%n

Reste(2,134234,5)

4

Exercice bonus 2 (*) : Écrire une fonction Diviseurs(a) qui renvoie la liste des diviseurs de a (sans tester tous les entiers <a !). Utilisez la factorisation en facteurs premiers.

def Diviseurs(a):
    div = Factorisation(a)
    actuel = []
    for (x,y) in div : actuel.append((x,0))
    reponse=[]
    finished = True
    while finished :
        k = 0
        finished = False
        while k<len(div) and not finished:
            (x,y),(x1,y1) = div[k], actuel[k]
            if y > y1: 
                actuel[k]=(x1,y1+1)
                finished = True
            else :
                actuel[k]=(x1,0)
                k+=1
        reponse.append(evaluate(actuel))    
    return reponse
    
    Diviseurs(60)