TP Python – Chiffrement, clés de contrôle et parcours circulaires
BTS SIO SISR 1re année – Mathématiques pour l'informatique – S07
Note
Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.
Exercice A – Puissance modulo n
Écris puissance_mod(a, k, n) qui calcule \(a^k \bmod n\) en réduisant à chaque tour (la valeur reste inférieure à \(n\)), sans utiliser ** ni pow.
J'anticipe. Pour puissance_mod(7, 100, 10), quelle réponse attends-tu ? Quelle propriété du cours te permet de la prévoir ?
def puissancepy-undmod(a, k, n):bksl-nl """Renvoie apy-strpy-strk modulo n en réduisant à chaque multiplication."""bksl-nl resultat = 1bksl-nl # À compléter : k fois, multiplier resultat par a puis réduire modulo nbksl-nl return resultat % nbksl-nlbksl-nl
Exercice B – Inverse modulo n
Écris inverse_mod(a, n) qui renvoie l'inverse de a modulo n (un entier entre 1 et n - 1) ou None s'il n'existe pas : essaie les valeurs x de 1 à n - 1.
Je comprends. Pour quelles valeurs de a la fonction renvoie-t-elle None quand n = 12 ? Compare avec le PGCD.
def inversepy-undmod(a, n):bksl-nl """Inverse de a modulo n (entre 1 et n-1), ou None s'il n'existe pas."""bksl-nl # À compléterbksl-nl return Nonebksl-nlbksl-nl
Exercice C – Chiffre affine
Complète chiffrer(texte, a, b) et dechiffrer(texte, a, b) pour un texte en majuscules (les autres caractères restent inchangés). ord("A") vaut 65 : le rang d'une lettre est ord(lettre) - 65.
def inversepy-undmod(a, n):bksl-nl for x in range(1, n):bksl-nl if (a py-str x) % n == 1:bksl-nl return xbksl-nl return Nonebksl-nlbksl-nldef chiffrer(texte, a, b):bksl-nl """Chiffre un texte en majuscules avec y = apy-strx + b (mod 26)."""bksl-nl resultat = ""bksl-nl for lettre in texte:bksl-nl if "A" <= lettre <= "Z":bksl-nl x = ord(lettre) - 65bksl-nl y = ... # à compléterbksl-nl resultat = resultat + chr(y + 65)bksl-nl else:bksl-nl resultat = resultat + lettrebksl-nl return resultatbksl-nlbksl-nldef dechiffrer(texte, a, b):bksl-nl """Déchiffre : x = a' py-str (y - b) (mod 26), où a' est l'inverse de a."""bksl-nl apy-undinv = inversepy-undmod(a, 26)bksl-nl resultat = ""bksl-nl for lettre in texte:bksl-nl if "A" <= lettre <= "Z":bksl-nl y = ord(lettre) - 65bksl-nl x = ... # à compléterbksl-nl resultat = resultat + chr(x + 65)bksl-nl else:bksl-nl resultat = resultat + lettrebksl-nl return resultatbksl-nlbksl-nl
Je comprends. Vérifie que dechiffrer(chiffrer(t, 5, 8), 5, 8) redonne t. Que se passe-t-il avec a = 13 ?
Exercice D – Clé du numéro de sécurité sociale
Écris cle_nir(numero) qui reçoit les 13 premiers chiffres (un entier) et renvoie la clé \(97 - (N \bmod 97)\).
def clepy-undnir(numero):bksl-nl """Clé de contrôle : 97 - (numero modulo 97)."""bksl-nl ...bksl-nlbksl-nl
Exercice E – ISBN-13
Écris isbn13_valide(code) qui reçoit un texte de 13 chiffres et renvoie True si la somme pondérée (poids 1, 3, 1, 3, …) est un multiple de 10.
def isbn13py-undvalide(code):bksl-nl """True si la somme pondérée (1, 3, 1, 3, ...) des 13 chiffres est un multiple de 10."""bksl-nl somme = 0bksl-nl for i in range(len(code)):bksl-nl chiffre = int(code[i])bksl-nl # À compléter : poids 1 si i est pair, 3 sinonbksl-nl return len(code) == 13 and somme % 10 == 0bksl-nlbksl-nl
Exercice F – Parcours d'une liste circulaire
Écris cases_visitees(n, k) qui renvoie l'ensemble des cases visitées en partant de 0 par sauts de k dans une liste de n cases, jusqu'à revenir en 0. Compare avec le PGCD.
def casespy-undvisitees(n, k):bksl-nl """Ensemble des cases visitées en partant de 0 par sauts de k (modulo n), jusqu'à revenir en 0."""bksl-nl cases = {0}bksl-nl position = k % nbksl-nl # À compléter : tant que la position n'est pas 0, l'ajouter puis avancer de k modulo nbksl-nl return casesbksl-nlbksl-nl