Category ArchivePython

Créer un fichier LaTeX avec Python

Dans un article précédent, je vous expliquais comment, dans un fichier \(\LaTeX\), on pouvait se servir de Python grâce à l’extension Pythontex.

Maintenant, je vais vous expliquer comment faire l’inverse, à savoir comment créer et compiler un fichier \(\LaTeX\) avec un programme Python.

L’objectif va être le même que dans l’article précédent (cas d’école) : créer 20 développements (avec double distributivité) aléatoires.

Créer un fichier TeX et le compiler sous Python

Importation des modules nécessaires

import os.path
import random
from sympy import Symbol
from sympy import expand
x=Symbol('x')

J’importe le module os car il va me servir à exécuter des commandes en lignes.

Ensuite, j’importe le module random car il est nécessaire dans notre contexte (dès lors qu’il y a choix aléatoire…).

J’utilise ensuite sympy pour les manipulations algébriques (c’est spécifique ici à ce que je souhaite faire). Je définis alors “x” comme le symbole désignant l’inconnue.

Construction du fichier

Le contenu du fichier va être défini par une succession de texte.

Définir le préambule

def preambule(*packages):
	p = ""
	for i in packages:
		p = p+"\\usepackage{"+i+"}\n"
	return p

Cette fonction a pour but d’appeler tous les packages nécessaires.

start = "\\documentclass[12pt,a4paper,french]{article}\n\\usepackage[utf8]{inputenc}\n"
start = start+preambule('amsmath','lmodern','babel')
start = start+"\\begin{document}\n\\begin{align*}\n"

end = "\\end{align*}\n\\end{document}"

On commence par définir la classe utilisée (avec les options souhaitées) ainsi que l’encodage. Puis, on appelle tous les packages souhaités. Enfin, on commence le document.

Génération des égalités

body = ""

for n in range(21):
    a = random.choice([1, -1]) * random.randint(2, 9)
    b = random.choice([1, -1]) * random.randint(2, 9)
    c = random.choice([1, -1]) * random.randint(2, 9)
    d = random.choice([1, -1]) * random.randint(2, 9)
    e = (a*x+b)*(c*x+d)
    eresultchain = str(expand(e)) # on convertit le résultat en chaîne de caractères
    eresultchain = eresultchain.replace('**','^') # on met au format TeX les exposants
    eresultchain = eresultchain.replace('*','') # on élimine les symboles '*'
    echain = str(e)
    echain = echain.replace('*','')

    body = body+echain+" & = "+eresultchain+"\\\\\n"

Il est ici nécessaire d’anticiper sur la syntaxe \(\LaTeX\) pour remplacer certains caractères…

Ecriture du fichier

container = start+body+end

file = "monfichier.tex"
if os.path.exists(file):
	os.remove(file)

fichier = open("monfichier.tex","x") # "x" pour la création et l'écriture
fichier.write(container)
fichier.close()

Compilation

Une fois le fichier créé, il est pratique de le compiler directement puis de l’afficher.

instructions = "pdflatex "+file#"
os.system(instructions)

readpdf = "START "+file[:-4]+".pdf"
os.system(readpdf)

Et voilà ! Une feuille d’exercices créée en à peine 2 secondes…

Le code complet

Les abonné.e.s de ce site trouveront le code complet sur cette page.

Python et fonction à nombre variable d’arguments

Voici une astuce qui pourra sans doute servir à plusieurs d’entre vous.

Une fonction peut quelques fois devoir prendre un nombre variable d’arguments. Par exemple, si l’on souhaite calculer le PGCD de plusieurs nombres, on aimerait que la fonction PGCD (par exemple) accepte 2, 3, 4, … arguments.

Voici sur un exemple comment faire:

def pgcd(*n):
	def _pgcd(a,b):
		while b!=0:
			a,b = b,a%b
		return a
	p = _pgcd(n[0],n[1])
	for x in n[2:]:
		p = _pgcd(p,x)
	return p

print(pgcd(165,515,225,65))

Alors ? On kiffe ?

Python et ensembles de Julia

L’ensemble de Julia est, pour un nombre complexe c donné, l’ensemble des points d’affixes \(z_0\) tels que la suite définie pour tout entier naturel n par \(z_{n+1}=z_n^2+c\) est bornée.

Selon les valeurs de c, on peut obtenir des ensembles plutôt jolis:

Pour les personnes abonnées à mathweb.fr, vous trouverez un code Python ainsi que les 10 images (sans marquage) sur cette page.

Un IDE Python sympathique

Quand on décide d’installer Python sur sa machine, il est par défaut accompagner d’un IDE (Integrated Development Environment) plus que basique. Il est suffisant, mais pas trop jolie et peu pratique (car si on ouvre une fenêtre contenant notre programme et si on exécute ce dernier, le résultat s’affiche dans la console, ce qui fait 2 fenêtres).

C’est la raison pour laquelle j’ai souhaité aujourd’hui changer d’IDE.

Quelques essais

Eclipse

J’ai commencé par télécharger Eclipse qui, soit-disant, est le must. Mais lors du lancement de l’installation, une fenêtre s’ouvrit pour me signaler qu’il fallait une plateforme JDK 7+. Je télécharge donc JDK11, mais même après cela, Eclipse ne put s’installer. N’étant pas du tout patient, je tenta un autre IDE…

Atom

Ayant entendu parlé d’Atom, je l’installai pour l’essayer… Mais je n’y ai rien compris (je ne dis pas que Atom est compliqué… je dis juste que je suis une grosse merde et que je n’ai pas réussi à comprendre comment compiler un programme Python). Moi, il me faut un truc simple et rapide d’utilisation car je n’ai pas que ça à faire de ma vie (rester des heures à essayer de comprendre comment fonctionne un logiciel); il faut que le bousin soit pédagogue avec ses utilisateurs, même les plus cons (comme moi), ce qui n’est pas le cas…

Sublime Text

Jamais 2 sans 3… J’essayai alors le logiciel au nom pourri… Et là ! Miracle !

Déjà, le téléchargement s’effectua en quelques secondes (programme très léger) et l’installation aussi. Et puis, en chargeant un programme Python, on voit tout de suite comment faire pour le compiler:

La compilation est rapide (un CTRL+B suffit), le design par défaut plus que correct (même si on peut le changer). Bref, cet IDE est top !

Malheureusement, il nécessite une licence. Pour le moment, il fonctionne mais on verra sur la durée… Je ne manquerai pas de vous tenir informé.e.s.

Ensemble de Mandelbrot et Python

Pour la faire courte, l’ensemble de Mandelbrot est l’ensemble des points du plan complexe d’affixe c tels que la suite définie par \( \left\lbrace\begin{array}{l} z_0=0\\z_{n+1}=z_n^2+c\end{array}\right. \) est bornée.

Cet ensemble peut être construit à l’aide de Python, et de son module pygame. La vitesse à laquelle l’ensemble est construit est remarquable! Sur mon ordinateur (16 Mo RAM, sous Windows, processeur Intel Core i5), cela ne met pas plus de 10 secondes pour afficher ceci:

Ensemble de Mandelbrot réalisé avec Python

Avec une autre suite, j’ai obtenu:

Fractale réalisée avec Python

Je vous l’accorde, elle est nettement moins esthétique que la première, mais je ne suis pas Julia, ni Fatou 🙂

Les abonné.e.s de mathweb.fr trouveront les codes Python de ces deux fractales sur cette page.

Initiation à la complexité algorithmique

Loin de moi l’idée de faire un article complet sur la notion de complexité, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur à la rentrée 2019), je me suis aperçu que cette notion allait pointer le bout de son petit museau perfide… Je voudrais donc par cet article familiariser les élèves avec elle.

C’est quoi la complexité d’un algorithme ?

C’est le nombre d’opérations et d’affectations faites. On appelle cela des opérations élémentaires. Prenons le programme Python suivant:

def convert(n):
    h = n // 3600
    m = (n - 3600*h) // 60
    s = n % 60
    return h,m,s

n = 102152

print("{} secondes = {} h {} min {} sec.".format(n,convert(n)[0],convert(n)[1],convert(n)[2]))

Dans la fonction “convert”, il y a :

  • 3 affectations (h, m et s)
  • 5 opérations (n//3600, 3600*h, n-3600*h, (n-3600*h)//60 et n%60)

La complexité de cette fonction est donc égale à 8.

Exercice 1

Montrer que la complexité de la fonction suivante est égale à 5.

def myFunction(n):
    if n%3 == 0:
        p = n/3 + 2
    else:
        p = n*2 + 1
    return p

Solution

il y a d’abord un test (if) dans lequel il y a une opération (n%3), ce qui nous fait pour le moment une complexité de 2.

Ensuite, quelle que soit l’issue du test, il y a 1 affectation (p) et 2 opérations (pour calculer p), soit une complexité augmentée de 3.

Au final, on obtient bien une complexité de 5.

Structures itératives

Dans un programme, il y a souvent des boucles. Nous allons voir un exemple avec une boucle “for”:

def recherche(l,x):
    for i in range(len(l)):
        if l[i]==x:
            return i
    return -1

l = "Bonjour."
x = "p"

print(recherche(l,x))

La fonction recherche a pour but d’afficher le rang où se trouve le caractère “x” dans la chaîne de caractères “l”, et affiche “-1” si ce dernier n’est pas trouvé.

  • Au niveau de la boucle for, il y a 1 addition (sur i), une affectation (i) et une comparaison (test si i<len(l));
  • dans la boucle for, il y a un test (if l[i]==x).

Au final, si n est la longueur de la chaîne de caractères, il y a 4n opérations élémentaires, qui correspond à la complexité de la fonction recherche.

Exercice 2

Calculer la complexité de la fonction somme définie dans ce programme:

def somme(n):
    s = 0
    for i in range(n+1):
        s += i
    return s

print(somme(100))

Solution

Il y a :

  • au début, 1 affectation (s = 0);
  • au niveau de la boucle for, 3 opérations élémentaires (affectation sur i, opération d’incrémentation sur i, test sur i);
  • dans la boucle for, il y a 2 opérations élémentaires (1 affectation sur s et une opération sur s).

Ainsi, il y a 5 opérations élémentaires dans la boucle, répétées n fois, plus la première (hors boucle). La complexité de la fonction somme est donc égale à 5n+1.

En général, on appelle T la complexité (initiale de Time).

Exercice 3

Calculer la complexité de la fonction mystere du programme suivant:

def mystere(n):
    m = 0
    for i in range(n):
        for j in range(i):
            m += i+j
    return m

print(mystere(100))

Solution

  • Il y a avant tout 1 affectation dès le début (m=0);
  • ensuite, au niveau de la boucle sur i, 3 opérations élémentaires;
  • au niveau de la boucle sur j, il y a 3 opérations élémentaires répétées i fois;
  • dans la boucle sur j, il y a 3 opérations élémentaires (1 affectation sur m, une somme sur m et une somme de i et j).

Ainsi, à part la première affectation, il y a 9 opérations élémentaires pour chaque valeur de j possible. Il y a:

  • 1 valeur possible de j quand i=0 (j=0);
  • 1 valeur possible de j quand i=1 (j=0);
  • 2 valeurs possibles de j pour i=2 (j=0 et j=1):
  • etc.
  • n-1 valeurs possibles de j pour i=n-1.

La complexité est donc égale à:$$\begin{aligned} & 1+9\times(1+1+2+3+\cdots+(n-1))\\=\ & 10+\frac{9n(n-1)}{2}\\=\ & \frac{1}{2}(9n^2-9n+20).\end{aligned}$$

Ordre de grandeur de la complexité

Nous le voyons dans l’exemple précédent, la complexité peut s’exprimer par un polynôme. Dans un tel cas, si n est relativement grand, on pourra assimiler la complexité à son ordre de grandeur. Par exemple ici, la complexité de la dernière fonction est de l’ordre de \(n^2\). On écrira alors:$$T_n=O(n^2).$$On dira ici que la complexité est quadratique.

Pour l’exercice 2, \(T_n=5n+1=O(n)\). On dira que la complexité est linéaire.

Fonction récursive

Une des fonctions récursives la plus simple est celle qui permet de calculer n! (la factorielle de n), c’est-à-dire \(2\times3\times\cdots\times n\).

def factorielle(n):
    if n == 0:
        return 1
    else:
        return n*factorielle(n-1)

Il y a un test pour commencer (sur n). Si le test est vrai, on s’arrête, sinon on effectue une opération (un produit) en faisant appel à la même fonction. Ainsi, si n est non nul, il y a 2 opérations élémentaires + le nombre d’opérations élémentaires de la fonction au rang n – 1.

Si \(T_n\) représente la complexité de la fonction factorielle(n) alors:$$T_n=T_{n-1}+2,\quad T_0=1.$$

La complexité est donc donnée par une suite arithmético-géométrique. C’est toujours le cas pour les fonctions récursives.

On peut alors montrer que \(T_n=2n+1=O(n).\)

Généralités

Si on considère une fonction toto(n) dans laquelle on fait appel à cette même fonction a fois et dans laquelle il y a b opérations élémentaires, si on note \(T_n\) sa complexité alors:$$T_n=aT_{n-1}+b.$$Ainsi, \(T_n=O(a^n)\). La complexité est alors exponentielle.

Exercice 4

Quelle est la complexité de la fonction suivante:

def fibo(n):
    if n<2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

Solution

Il y a 2 opérations élémentaires (un test sur n et une addition de fibo(n-1) et fibo(n-1)) donc:$$T_n=T_{n-1}+T_{n-2}+2,\quad T_0=T_1=1.$$ La complexité est donc une suite linéaire d’ordre 2 et d’équation caractéristique:$$r^2-r-1=0$$ de solutions \(r_1=\frac{1+\sqrt5}{2}\) et \(r_2=\frac{1-\sqrt5}{2}\). Comme \(|r_1|>|r_2|\), une propriété nous dit que la complexité de la fonction fibo(n) est:$$T_n=O(r_1^n).$$La complexité est alors exponentielle.

Python, turtle et un arbre

Je ne suis pas très fan du module turtle, car je préfère la programmation numérique, mais il faut bien avouer que ce module est pratique pour dessiner des schémas récursifs, comme les fractales.

Je me suis donc mis à la recherche d’un code donnant un tel schéma pour tenter de me familiariser avec le module. J’avais une idée bien précise : celle d’un arbre fractal, que j’avais vu quelque part.

Après quelques recherches, je suis enfin tombé sur le code suivant (que je me suis permis de commenter):

from turtle import *

angle = 30
color('#3f1905')

def arbre(n,longueur):
    if n==0:
        color('green')
        forward(longueur) # avance
        backward(longueur) # recule
        color('#3f1905')
    else:
        width(n)
        forward(longueur/3) #avance
        left(angle) # tourne vers la gauche de angle degrés
        arbre(n-1,longueur*2/3)
        right(2*angle) # tourne vers la droite de angle degrés
        arbre(n-1,longueur*2/3)
        left(angle) # tourne vers la gauche de angle degrés
        backward(longueur/3) # recule

hideturtle() # cache la tortue
up() # lève le stylo
right(90) # tourne de 90 degrés vers la droite 
forward(300) # avance de 300 pixels
left(180) # fait un demi-tour
down() # pose le stylo
arbre(11,700) # exécute la macro
showturtle() # affiche la tortue
mainloop()

qui donne ceci:

Arbre fractal réalisé avec Python avec un angle de 30°

Mais attention… Le dessin met un certain temps avant d’être fini (par exemple, sur mon ordinateur 16 Mo de RAM, processeur Intel Core i5, il met une vingtaine de minutes… arf !)

Si on modifie l’angle (disons pour le mettre à 50°), on obtient ceci:

Arbre fractal réalisé avec Python avec un angle de 50°

Et avec un angle de 110° :

Arbre fractal réalisé avec Python avec un angle de 110°

N’est-il pas choupinou ? 🙂

Vous pouvez remarquer dans le code la fonction récursive : c’est une notion que l’on verra en NSI (nouveau lycée)… mais prévue en cycle de maturité (en Terminale quoi !)… même si je n’ai pas pu résister à l’envie d’en mettre dans mon livre d’exercices corrigés qui sortira en version papier pour la rentrée 2019.

Une fonction récursive est une fonction qui fait appel à elle-même dans sa définition. On retrouve ce genre de fonction par exemple pour calculer le pgcd de deux nombres:

def pgcd(a,b):
    if b==0:
        return a
    else:
        r=a%b
        return pgcd(b,r)
 
print(pgcd(56,42))

Ici, la récursivité s’appuie sur la propriété du pgcd qui stipule que:$$\text{pgcd}(a,b)=\text{pgcd}(b,r)$$où \(a = bq + r,\ 0\leq r < b\).

Les mathématiques sont donc très importantes pour construire des algorithmes (et par suite des programmes) performants. En effet, on aurait très bien pu calculer le pgcd de la manière suivante:

def pgcd(a,b):
    while b<>0:
        r=a%b
        a,b=b,r
    return a
 
print(pgcd(56,42))

Pour comparer deux algorithmes, on parle souvent de complexité. Cet article ne parle pas de cette notion, mais sachez tout de même que la complexité d’une fonction récursive est donnée par une suite arithmético-géométrique. Dans la fonction pgcd, il y a 2 instructions élémentaires (le test sur b et l’affectation de r). La complexité \(C_n\) est donc égale à \(2+C_{n-1}\), où \(C_{n-1}\) est celle de la fonction pgcd(b,r). On démontre alors que la complexité de la fonction récursive est de l’ordre de O(n) [complexité linéaire]. En fait, la complexité est linaire dans le pire des cas (quand a et b sont deux nombres successifs de la suite de Fibonacci), car dans les autres cas, la complexité est logarithmique [O(ln(n))].

L’évaluation moyenne de la complexité de l’algorithme d’Euclide version récursive est assez compliquée. Le nombre d’appels moyen de la fonction pgcd est:$$\frac{12\ln(2\ln n)}{\pi^2}+1,47.$$

http://imss-www.upmf-grenoble.fr/prevert/Prog/Complexite/euclide.html

La complexité de l’algorithme non récursif est quasi-identique à sa version récursive.


La version récursive de l’algorithme d’Euclide est peut-être un peu plus facile à écrire que la version itérative. Les deux versions ont fondamentalement la même complexité, avec un petit avantage à la version itérative, car l’appel d’une fonction n’est pas gratuit.

https://www.labri.fr/perso/betrema/deug/poly/euclide.html

Mais là, je m’égare… Saint-Lazare !

Python et le nombre d’or

Voici un article qui est abordable dès le lycée.

La suite de Fibonacci

Imaginons une suite de nombre qui commence par “1” et “1”.

On souhaite que le nombre qui vient juste après soit égal à la somme des deux derniers nombres. Ainsi, le 3ème nombre est égal à 1+1, soit “2”. Après “2”, il y a 2+1=3, puis après ce “3”, il y a 3+2=5.

Comprenez-vous maintenant comment on calcul les termes de cette suite de nombres ? On prend toujours les deux derniers, on les ajoute et ça nous donne le suivant.

Comme ce procédé est répétitif, on va pouvoir utiliser un programme pour trouver tous les nombres de cette suite. En Python, cela donne :

F = [1,1]
for n in range(30):
    F.extend([F[n+1]+F[n]])

print(F)

La première ligne définie une liste (de nombres) que l’on initialise avec les deux nombres desquels on part (donc ici, “1” et “1”). On a ainsi F[0]=1 et F[1]=1 (le premier item d’une liste est toujours indicé à 0).

Ensuite, on créé une boucle “Pour” afin de calculer ici 30 termes de plus : quand on écrit “for n in range(30)“, cela signifie que la variable n va prendre 30 valeurs entières en partant de 0.

Dans cette boucle, on calcule la somme des deux derniers termes de la liste L, puis on ajoute le résultat à la liste (c’est la méthode extend : on étend la liste avec la valeur trouvée).

Une fois sorti.e.s de la boucle, on affiche la liste, ce qui nous donne:

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309]

Le nombre d’or

Maintenant, comme je suis quelqu’un de très bizarre (no comment, thanks!), j’ai envie de calculer les quotients successifs de deux termes consécutifs de cette suite. Je vais utiliser le code suivant:

for n in range(31):
    print(F[n+1]/F[n])

ce qui m’affiche:

 1.0
2.0
1.5
1.6666666666666667
1.6
1.625
1.6153846153846154
1.619047619047619
1.6176470588235294
1.6181818181818182
1.6179775280898876
1.6180555555555556
1.6180257510729614
1.6180371352785146
1.618032786885246
1.618034447821682
1.6180338134001253
1.618034055727554
1.6180339631667064
1.6180339985218033
1.618033985017358
1.6180339901755971
1.618033988205325
1.618033988957902
1.6180339886704431
1.6180339887802426
1.618033988738303
1.6180339887543225
1.6180339887482036
1.6180339887505408
1.6180339887496482

Ne remarquez-vous pas quelque chose ? Ces quotients semblent se rapprocher d’un nombre, dont la valeur approchée au millième est 1,618. C’est ce nombre que l’on appelle le nombre d’or.

Dans la mesure où Python affiche 16 décimales, je me demande à partir de quel rang j’obtiendrai une valeur approchée du nombre d’or avec une précision de \(10^{-16}\). Je vais utiliser ce code:

F = [1,1,2,3]
n = 3

while (abs(F[n-2]/F[n-3]-F[n]/F[n-1])>10**(-16)):
    u = F[n]+F[n-1]
    F.extend([u])
    n +=1
    
print(F[n]/F[n-1])

Je demande ici à calculer les termes successifs de la suite de Fibonacci tant que la valeur absolue de la différence de deux quotients consécutifs est supérieure à \(10^{-16}\).

Ainsi, la valeur affichée sera une valeur approchée du dernier quotient calculé, qui sera aussi une valeur approchée du nombre d’or.

On obtient ici:

1.618033988749895

Ce nombre d’or est noté par la lettre grecque: \[ \varphi \approx 1,618033988749895.\]

Aller plus loin…

On peut dire beaucoup de choses sur le nombre d’or, mais on peut aussi préciser qu’il existe un nombre d’argent (appelé ainsi par Gilles HAINRY, professeur à l’université du Mans à l’époque des faits, donc en 1996). Dans un cas général, on parle de nombres de métal.

Pour en savoir plus, je vous invite à regarder l’excellent ouvrage “Ainsi de suites”, écrit par…. Oh tiens ! Ecrit par moi 🙂 ! Il est téléchargeable gratuitement sur ce site sur la page suivante :https://www.mathweb.fr/euclide/ouvrages-personnels-de-mathematiques/

Chiffrement de Hill en Python

Nous allons encore une fois parler cryptographie dans cet article. Dans l’article précédent, je vous parlais du chiffrement affine, le chiffrement le plus nul après le chiffrement de César, mais cette fois-ci, on va lever le niveau…

Les prérequis

Pour chiffrer un message avec cette méthode, il nous faudra connaître les matrices ainsi que les opérations de base qui s’y rapportent, mais aussi la notion de modulo…

Nous allons nous basé sur un alphabet (un ensemble constitué d’un certain nombre de caractères). Pour ma part, j’ai pris :

alphabet=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',"'","ù","é","è","à","ç","-","ê"," ","."]

De plus, comme il y a pas mal de calculs d’algèbre linéaires, j’utilise le module numpy.

Condition nécessaire et suffisante

La clé de chiffrement est une matrice. Pour pouvoir chiffrer, et surtout déchiffrer, il faut que le déterminant de cette matrice ait un inverse modulo le nombre de caractères de notre alphabet. Il faut donc, après saisie de la matrice, tester cette condition. Rappelons que le déterminant (que je vais noter d) est inversible modulo n s’il existe un entier x compris entre 0 et n-1 tel que dx = 1 mod n.

De plus, le message à chiffrer doit comporter un nombre de caractères multiple de la dimension de la matrice (qui doit être carrée). Donc ici, deux possibilités :

  • soit on demande à l’utilisateur un message ayant un nombre convenable de caractères, ce qui n’est pas très pratique,
  • soit on complète le message par des espaces vides afin que le nombre de caractères soit au final un multiple de la dimension de la matrice.

C’est la seconde solution que j’utilise.

Principe du chiffrement

Pour faire simple, je vais prendre une matrice \(2\times2\), par exemple : $$A=\begin{pmatrix}3&7\\2&13\end{pmatrix}$$et un mot de deux lettres, par exemple “MA”.

Première étape

J’attribue à chaque lettre de mon mot un nombre (le rang de la lettre dans l’alphabet). Donc ici, “M” correspond à 12 et “A”, à “0”. Je créé ainsi un vecteur:$$V=\begin{pmatrix}12\\0\end{pmatrix}.$$

Deuxième étape

Je multiplie la matrice-clé par le vecteur ainsi obtenu:$$\begin{pmatrix}3&7\\2&13\end{pmatrix}\begin{pmatrix}12\\0\end{pmatrix}=\begin{pmatrix}36\\24\end{pmatrix}.$$

Troisième étape

Je prend les coefficients du résultat modulo le nombre de caractères dans l’alphabet. Comme ici c’est 62, ça ne change rien aux nombres obtenus.

Quatrième étape

Je convertis les nombres en caractères en prenant les lettres qui correspondent aux rangs obtenus. Ici, 36 correspond au caractère “k”, et 24 à la lettre “Y”.

Le message chiffré est alors : “kY”.

Principe du déchiffrement

Il est le même que celui du chiffrement, en prenant comme matrice l’inverse modulo n de la matrice de chiffrement.

Première étape

On calcule le déterminant de la matrice de chiffrement A. Pour mon exemple, on trouve :$$\det A=25.$$

Ensuite, on exprime la matrice inverse sous la forme :$$A^{-1}=\frac{1}{\det A}B$$où \(B\) doit être trouvée. Pour nous,$$A^{-1}=\frac{1}{25}\begin{pmatrix}13&-7\\-2&3\end{pmatrix}.$$

Deuxième étape

On cherche l’inverse du déterminant modulo le nombre de caractères dans l’alphabet. On cherche donc ici l’inverse de 25 modulo 62. On trouve 5 car \(25\times5=125=1\mod 62\).

Donc on peut écrire:$$A^{-1}=5\begin{pmatrix}13&-7\\-2&3\end{pmatrix}.$$

Troisième étape

On calcule modulo le nombre de caractères dans l’alphabet les coefficients de la matrice inverse. Ici, on obtiens :$$A^{-1}=\begin{pmatrix}65&-35\\-10&15\end{pmatrix}\equiv\begin{pmatrix}3&27\\52&15\end{pmatrix}\mod62.$$

Quatrième étape

On chiffre le message chiffré à l’aide de la matrice inverse. Donc ici, si on part du message “kY”, qui correspond au vecteur \(\binom{36}{24}\), on a :$$\begin{pmatrix}3&27\\52&15\end{pmatrix}\begin{pmatrix}36\\24\end{pmatrix}=\begin{pmatrix}756\\2232\end{pmatrix}\equiv\begin{pmatrix}12\\0\end{pmatrix}\mod62.$$On retrouve bien le rang des lettres “M” et “A”.

Résultat en Python

J’ai ici converti en fichier exécutable le programme Python, et voici les captures d’écran:

Téléchargement des fichiers

Pour les abonné.e.s de mathweb.fr, j’ai mis tous les fichiers dans un ZIP sur cette page. Pour exécuter directement le programme, double-cliquez sur le fichier Hill.py.

Créer un exécutable sous Windows à partir d’un programme Python

Si vous êtes comme moi, vous êtes sûrement frustrés d’avoir créé un beau programme Python et de ne pas l’avoir en exécutable sous Windows.

Dans cet article, je vais vous montrer comment transformer votre fichier .py en fichier .exe.

Installation du module cx_Freeze

Allez en ligne de commande. Pour cela, allez dans la recherche Windows et tapez “cmd”.

Ensuite, tapez la commande suivante :

python -m pip install cx_Freeze --upgrade

Si tout se passe bien, un message positif apparaîtra. Sinon… ben dommage ! 🙂

Création d’un programme Python

Je vais partir d’un programme que j’avais déjà exposé, celui d’un chiffrement/déchiffrement affine, en l’améliorant un peu :

 alphabet=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',"'","ù","é","è","à","ç","-","ê"," "]

# Calcul du pgcd de a et b

def pgcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

# fonction de chiffrement affine

def chiffrementAffine(a,b,L):
        x=alphabet.index(L)
        y=(a*x+b)%len(alphabet)
        return alphabet[y]

# Calcul de l'inverse d'un nombre modulo 26

def inverse(a):
        x=0
        while (a*x%len(alphabet)!=1):
                x=x+1
        return x

# Fonction de déchiffrement

def dechiffrementAffine(a,b,L):
    x=alphabet.index(L)
    y=(inverse(a)*(x-b))%len(alphabet)
    return alphabet[y]
                

# Affichage du mot chiffré

def crypt(M,a,b):
    if (pgcd(a,len(alphabet))==1):
        mot = [chiffrementAffine(a,b,i) for i in M]
        return "".join(mot)
    else:
        return "Chiffrement impossible. Veuillez choisir un nombre a premier avec"+str(len(alphabet))+"."

# Affichage du mot déchiffré

def decrypt(M,a,b):
    if (pgcd(a,len(alphabet))==1):
        mot = [dechiffrementAffine(a,b,i) for i in M]
        return "".join(mot)
    else:
        return "Déchiffrement impossible. Le nombre a n'est pas premier avec"+str(len(alphabet))+"."

# Menu

def menu():
    print('Menu du jour...\n----------------')
    print('1. Chiffrer un message')
    print('2. Déchiffrer un message\n-----------------------\n')
    choix = int(input('Quel est votre choix ? '))
    if choix == 1:
        chiffrer()
    elif choix == 2:
        dechiffrer()
    else:
        print('Can you be serious please... ?\n')
        menu()

# Retour au menu ?

def return_menu():
    rep = input('\nSouhaitez-vous revenir au menu (O/N) ? ')
    if rep.upper() == 'N':
        the_end()
    elif rep.upper() == 'O':
        menu()
    else:
        print('Can you be serious please... ?\n')
        return_menu()
# the_end()

def the_end():
    print("Ok. C'est vous qui voyez... See you soon !")
    
# chiffrer

def chiffrer():
    msg = input('Entrez le message à chiffrer : ')
    a = int(input('Entrez la première clé : '))
    b = int(input('Entrez la seconde clé : '))
    print('Le chiffrement donne : ',crypt(msg,a,b))
    return_menu()

def dechiffrer():
    msg = input('Entrez le message à déchiffrer : ')
    a = int(input('Entrez la première clé : '))
    b = int(input('Entrez la seconde clé : '))
    print('Le chiffrement donne : ',decrypt(msg,a,b))
    return_menu()

menu()

Ce programme, je vais le sauvegarder sous le nom chiffrement.py.

Création d’un programme de transformation

Je vais créer maintenant un autre programme Python:

from cx_Freeze import setup, Executable

setup(
    name = "ChiffrementAffine",
    version = "0.1",
    description = "Chiffre et déchiffre un message",
    executables = [Executable("chiffrement.py")]
)

Je vais sauvegarder ce programme sous le nom setup.py dans le même répertoire que chiffrement.py.

Construction de l’exécutable

En ligne de commande, je vais dans le répertoire où se trouvent mes deux fichiers Python, puis je tape :

python setup.py build

Cela peut prendre quelques secondes si c’est la première fois que vous entrez cette ligne de commande. À la fin, on doit obtenir un écran comme celui-ci:

Capture d’écran : terminal Windows

Dans le répertoire où se trouvent les fichiers Python, un répertoire nommé build s’est créé, dans lequel se trouve un répertoire dont le nom ressemble à exe.win32-3.6 , dans lequel se trouve le fichier exécutable, ainsi que plein de fichiers dll.

Et voilà ! Votre fichier exécutable est prêt !

Pour les abonné.e.s de ce site, je mets le ZIP correspondant sur cette page.