La question de factorisation des entiers est au coeur de nombreux problèmes mathématiques. En sage, on dispose de la commande factor.
factor(56)
Le résultat est certes joli, mais en pratique on veut souvent réutiliser le résultat. Pour cela, on peut le convertir en liste.
f=factor(56);
list(f)
Sage est très fort et sait factoriser rapidement de grands entiers. Faire quelques tests.
factor(10^100+17)
Exercice. Pour voir que ce n'est pas si facile d'aller aussi vite, écrire vous même un algorithme de factorisation naïf (en testant les divisions successives).
N.B. Naïf ne veut pas dire qu'on ne peut pas être malin. Pensez notamment aux bornes des diviseurs à tester!
Pour alléger votre code, vous pouvez ne pas regrouper les facteurs multiples.
def factorise(n):
return []
Jusqu'à quelle taille d'entiers arrive t-on à factoriser?
Une question liée à la précédente est celle du test de primalité. On a vu en cours que le critère de Fermat permet de montrer que certains entiers ne sont pas premiers sans avoir à exhiber une factorisation explicite. On se propose de tester cette méthode.
Avant de commencer: à votre avis, quelle différence fondamentale y a t-il entre les deux calculs suivants qui explique la différence de temps d'exécution?
time(254^977821 %977821)
time(Mod(254,977821)^977821)
Qu'en déduit-on sur 977821?
Ecrire une fonction Fermat(a,n) qui renvoie vrai si $a$ vérifie la propriété de Fermat dans $\mathbf Z/n\mathbf Z$ et faux sinon.
def Fermat(a,n):
return true
Fermat(4,97)
On décide de procéder comme suit: pour décider si $n$ est pseudo-premier, on tire au hasard 5 éléments de $\mathbf Z/n\mathbf Z$ et on teste s'ils vérifient la propriété de Fermat. S'ils passent tous le test, on le déclare pseudopremier (avec une certaine probabilité).
randint?
def pseudo_prem(n):
return true
Faîtes quelques tests. Comparer par exemple la liste des nombres "pseudo-premiers"$\leq 1000$ que vous trouvez ainsi avec la liste des nombres premiers que Sage peut vous donner.
P=Primes()
[P[i] for i in range (200) if P[i]<1000];
N.B: Au début des années 2000, 3 étudiants indiens de votre âge ont montré qu'il existe un algorithme polynomial permettant de tester si un entier est premier ou non. "Primes is in P."
On note $\varphi$ la fonction d'Euler. Ainsi $\varphi(n)$ compte le nombre d'éléments inversibles de $\mathbf Z/n\mathbf Z$.
Ecrire une fonction phi qui calcule cette valeur à partir d'une factorisation de $n$.
def phi(n):
f=factor(n)
return 0
Parfois, on peut être amené à avoir besoin de la liste de tous les éléments de $(\mathbf Z/n \mathbf Z)^\times$.
Ecrire une fonction liste_inversibles(n) qui renvoie la liste des inversibles de $\mathbf Z/n \mathbf Z$.
def liste_inversibles(n):
return []
Pour coder un message avec RSA, il faut d'abord convenir d'une façon de représenter les messages par des nombres qu'on pourra ensuite crypter en utilisant RSA. Pour simplifier, on se limite à des messages n'utilisant que les lettres "a", "b",... "z" et " "(l'espace). Donc PAS DE MAJUSCULES, d'ACCENTS, etc...
On a ainsi 27 caractères, qu'on associe aux entiers de 0 à 26 comme suit: a=1, b=2, .., z=26, " "=0. Il est alors naturel d'encoder une chaîne de caractères par l'entier correspond en base 27. Ainsi, le mot "abc" est encodé par l'entier $1\times 27^2+2\times 27+3$.
En SAGE, une chaîne de caractères (string) est une liste de lettres auxquelles on peut accéder comme dans une liste.
mot="a sjkg hdfjkg"
mot[5], mot[1],mot[0]
On peut renvoyer le code ascii de chaque lettre grâce à la fonction ord().
ord('a'), ord("b"), ord(' ')
On donne donc les fonctions Lettreanombre() et nombrealettre() suivantes.
def lettreanombre(l):
if l==' ':
return 0
else:
return ord(l)-96
lettreanombre('e'), lettreanombre("z")
def nombrealettre(n):
if n==0:
return ' '
else:
return chr(n+96)
nombrealettre(0)
Ecrire une fonction encode() qui prend une chaîne de caractère et l'encode selon le principe précédent.
def encode(s):
return 0
encode("abc")
Ecrire une fonction decode() qui fait l'inverse. (N.B.:on peut concaténer des lettres grâce à +: 'a' +'b'="ab").
def decode(n):
return ""
On en vient à RSA proprement dit. Codez la phrase: "l algebre effective c est trop cool". On devrait trouver 55670025528737887382431553890564338447362361699750 (il y a 50 chiffres).
log(55670025528737887382431553890564338447362361699750.,10)
Voici ma clé RSA que je donne à tout le monde: cle est le produit de deux nombres premiers que je tiens secret mais dont je donne le produit et exp est un exposant que j'ai choisi pour être premier avec $\varphi(cle)$.
cle=51564215854895166241100000000000035579308939877664706359
exp=6753790093096013771
Envoyez moi la phrase précédente codée. Vous devriez trouver:'qixllymaugladgrhwmyeiakpqosmqdkhmfxsszp'
Je n'ai pas été très malin, ma clé n'a que 55 chiffres. C'est trop peu. Vous pouvez décoder les messages que vous interceptez en utilisant judicieusement l'ordinateur. Faîtes le avec le message suivant:
message="fihhn kir merxmxlbzsqkyvcvpecldodleohxy"
À vous de vous créer une clé publique et un exposant. Il vous faut pour cela trouver 2 nombres premiers grands. Faîtes le.
next_prime?
A partir de là, comment calculer $\varphi(n)$ et trouver un exposant premier à $\varphi(n)$?
Je me suis finalement rendu compte que vous lisiez mon courrier (au passage, ça vous fait moins 5 points!) et j'ai augmenté la taille de ma clé secrète (environ 200 chiffres). Du coup, je me suis dit que je pouvais économiser sur la taille de l'exposant (ça fait moins de calculs pour chiffrer un message).
cle=34999999999999999999999999999999999999999999999999999999999999999999999943580545084716072139932442339500000000000000000000000000000000000000000000000821260436490287444342737236448339920284176974726843
exp=3
Montrez que ce n'est pas une bonne idée. Déchiffrez le message suivant (que vous conjecturez n'être pas trop long.)
message='lcyjtiklnclxgnttwtiuilfgvpaloynzsaadvzdbmpogcjnzxn qgczihpvlclpvaosnmcyymflgazzoswlggiifafhz kq'