Rabin
On considère un cryptosystème de Rabin pour l'entier de 1024
bits
n = 27328417631308277322150562883314533200963002826716705199968875674106406752147424222024338127563628593224661592571938485301935882942995461145895711114923374531636454291853327561820612951870422339965236147439814490182689636048215824374569331866443582899661940664297395527208577159582046566117830509217529095109
Pour assurer la sécurité du système, on impose de
ne chiffrer que des messages dont les 10 derniers bits sont
1010101010
.
Pour un chiffré c = [m^2,kronecker(m,c),m%2]
,
c->dechiffre(c)
renvoie le message m
, s'il satisfait
à la condition sur les 12 derniers bits.
Déterminer le plus petit facteur de n
.
Format
Vous devez écrire un programme main.gp
en Pari/GP dont l'exécution via
gp -fq < main.gp
affiche (uniquement) la solution cherchée.
taper make check
permet de vérifier que votre solution est bonne.
Veillez à mettre des commentaires sur votre démarche et sa validité
dans le fichier main.gp
.
Validation
Il reste à faire un commit et à envoyer votre solution pour l'enregistrer
git add main.gp
git commit -m 'ma solution'
git push