Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Crypto : factorisation par calcul de PGCD
Posté par direigun
Bonjour,
On buche sur un petit exercice de crypto sans voir du tout comment en venir à bout. Voilà l'énoncé :
Soit N = 16459. En remarquant que 12534²
1 (mod N), factoriser N par un calcul de PGCD.
Si quelqu'un peut nous aiguiller un peu, ca serait sympathique.
Merci d'avance
Bonjour,
a²-1=(a-1)(a+1)
12533*12535=k*16459;
ou
comme 12534=16459-3925;
(-3925)²est congru à 1 modulo 16459,
(3925)²est congru à 1 modulo 16459
3926*3924=k'*16459
on peut diviser par 8 et 9 car 16459 divise le cote droit et est premier avec 8 et 9
1963*109=k"*16459
1963 se divise par 13 et 16459 ne se divise pas par 13
151*109=K*16459 et là stop 151*109=16459
mais c'est plus du th gauss que du pgcd