puisque on veut m'apprendre des choses, sortons la grosse artillerie ;-) .
Commençons par la fin.
NP signifie Non Polynomial, plus exactement non deterministe en un temps polynomial. On sait deja que P et NP sont des ensembles disjoint, mais la conjecture est que NP et NP-complet soit disjoint aussi, ce qui n'arrange rien, mais tous laisse penser que cela est vrai meme si il n'y a aucune demonstration.
Je parlais de factorisation pas d'autre chose. Pour factoriser un nombre N, il faut connaitre les nombres premiers qui peuvent le composer, donc il faut factoriser tous les nombres avant pour savoir si ils sont premiers ou non.
De plus, je parlais de test total de primalité, hors il n'existe aucun test total de primalité qui soit dans P, cad qui soit calculable en un temps polynomiale.
Le test de Rabin-Miller n'est pas fiable à 100%, il existe une marge d'erreur fonction du nombre d'iteration, plus il y a de tests et plus la precision est grande mais elle n'est jamais de 100%. Les autres tests comme Solovay-Strassen et Lehmann sont moins performant.
Les seules methodes fiable à 100% sur un test de primalité reste la factorisation, et cela passe par un de ces algorithmes déja connus :
- le crible quadratique
- les courbes elliptiques
- l'algorithme de monte carlo
- les fractions continues
- la tentative de division
je donne l'algo de RSA pour le principe :
soit 2 nombres premiers p et q, soit n tel que :
n= p * q
soit e un nombre aleatoire tel que e soit premier avec (p-1)*(q-1) , soit d tel que :
e * d = 1 mod (p-1)*(q-1)
pour chiffrer m en c, il suffit de faire :
c = m^e mod n
pour dechiffrer c en m, il suffit de faire :
m = c^d mod n
Mes references sont introduction à l'algorithmique de Cormen Leiserson et Rivest , Course in Number Theory and Cryptography de Koblitz, et the art of computer programming de Knuth.
[^] # Re:theorie des nombres, algorithmique de base, et algo de RSA
Posté par Mouns . En réponse à la dépêche Le RSA en danger. Évalué à 4.
Commençons par la fin.
NP signifie Non Polynomial, plus exactement non deterministe en un temps polynomial. On sait deja que P et NP sont des ensembles disjoint, mais la conjecture est que NP et NP-complet soit disjoint aussi, ce qui n'arrange rien, mais tous laisse penser que cela est vrai meme si il n'y a aucune demonstration.
Je parlais de factorisation pas d'autre chose. Pour factoriser un nombre N, il faut connaitre les nombres premiers qui peuvent le composer, donc il faut factoriser tous les nombres avant pour savoir si ils sont premiers ou non.
De plus, je parlais de test total de primalité, hors il n'existe aucun test total de primalité qui soit dans P, cad qui soit calculable en un temps polynomiale.
Le test de Rabin-Miller n'est pas fiable à 100%, il existe une marge d'erreur fonction du nombre d'iteration, plus il y a de tests et plus la precision est grande mais elle n'est jamais de 100%. Les autres tests comme Solovay-Strassen et Lehmann sont moins performant.
Les seules methodes fiable à 100% sur un test de primalité reste la factorisation, et cela passe par un de ces algorithmes déja connus :
- le crible quadratique
- les courbes elliptiques
- l'algorithme de monte carlo
- les fractions continues
- la tentative de division
je donne l'algo de RSA pour le principe :
soit 2 nombres premiers p et q, soit n tel que :
n= p * q
soit e un nombre aleatoire tel que e soit premier avec (p-1)*(q-1) , soit d tel que :
e * d = 1 mod (p-1)*(q-1)
pour chiffrer m en c, il suffit de faire :
c = m^e mod n
pour dechiffrer c en m, il suffit de faire :
m = c^d mod n
Mes references sont introduction à l'algorithmique de Cormen Leiserson et Rivest , Course in Number Theory and Cryptography de Koblitz, et the art of computer programming de Knuth.
voila ;-p