factorisation
dans Arithmétique
Je sais que dans le cas général, tous les algorithmes de factorisation connus sont en temps exponentiel. Mais pourquoi serait-il impossible de trouver un algorithme de factorisation en temps polynomial lorsqu'on sait que le nombre à factoriser est un produit de deux nombres premiers ?
lfr
lfr
Réponses
-
Voyons alors, l'algorithme RSA est-il un contre-ex ?
-
L'algorithme RSA n'est pas un algorithme de factorisation.
Factoriser un entier: trouver tous ses facteurs.
Va factoriser $630000000000000000000000000000000000000000000000000000000000000000000000000\\
000000000000000000019837638200000000000000000000000000000000000000000000000000000000000\\
000000000000000000000000000153722107762559$
avec l'algo RSA B-)- -
Je n'ai pas eu de réponse à ma question. lfr
-
En tant que béotien, je suis partagé entre deux réponses contradictoires :
-- personne n'a prouvé qu'il est impossible qu'existe un algorithme en temps polynomial, même si l'espoir semble mince (à qui au fait ?) ;
-- factoriser un entier, c'est essentiellement trouver un facteur premier et c'est plus difficile lorsque le facteur est grand : cela n'apporte rien de savoir qu'il n'y en a que deux. -
En temps sous-esponentielle je crois.
La réponse à ta question n'est pas connue à l'heure d'aujourd'hui sauf erreur.
Il existe des algorithmes de factorisation rapide mais pour ordinateur quantique. -
Le fait de savoir qu'il n'y a que deux facteurs nous assure que le nombre est de la forme :
p = a2 - b2 = (a+b)(a-b)
Si en plus on sait que (a+b) et (a-b) sont des nombres premiers, ce n'est pas une mince information.
lfr -
Lfr:
J'aimerais bien que tu me trouves $a,b$ entiers naturels tels que: $2\times 3=(a-b)(a+b)$ B-)-ce n'est pas une mince information. a écrit:
Cela permet d'obtenir un algorithme de factorisation mais qui n'est pas très efficace, en général, rien de plus à ma connaissance. -
Effectivement, si le nombre à factoriser est pair, la solution est triviale.
Supposons donc qu'il soit impair, et appelons n et p ses deux facteurs premiers.
Appelons encore s leur somme : s=n+p et décidons que p<n.
n et p sont les deux solutions de l'équation : x2 -sx +np =0
On connait np mais pas s=n+p.
On sait aussi que 2n=s+sqrt(s2-4np) et 2p=s-sqrt(s2-4np)
On sait de plus que n>sqrt(np) et que p<sqrt(np)
Comme n et p sont des entiers, il faut que sqrt(s2-4np) soit aussi un entier.
L'algorithme peut chercher la plus petite valeur de s, à partir de 2.sqrt(np), qui assure cette condition.
Plus n et p seront proches l'un de l'autre, plus l'algorithme sera rapide. -
C'est une bonne idée à partir de laquelle on fait une méthode plus efficace que la méthode naïve consistant à diviser par tous les nombres impairs. Mais ça reste impraticable.
Exemple avec deux nombres premiers (« proches ») à 41 chiffres :
\[\begin{array}{l}p=77483003332019368676353829123307788143247\\
q=82233037748596769504706310607818114256033\end{array}\]
La différence entre $\sqrt{pq}$ et $p$ est plus grande que $10^{39.3}$. Cela signifie que lorsqu'on part de la racine carrée, avant d'atteindre $p$ ou $q$, il faudra plus de $10^{39}$ essais. Soit, avec un ordinateur qui ferait $10^{12}$ opérations par seconde, $10^{23}$ secondes : déraisonnable.
(Rappel : il y a $3\times10^7$ secondes par an environ.) -
Comme je suis au chomage et que j'ai du temps libre,
je continue à chercher toutes les informations qu'on peut déduire des hypothèses.
On sait que tout nombre premier est congru à 1,5,7 ou 11 modulo 12.
On a toujours p^2 = q^2 = 1 [12] car p et q sont premiers.
Sur une table de multiplication modulo 12, on peut voir que pq = 1 ou -1 [12]
J'appelle d la différence positive de p et q, s étant leur somme.
On a : p^2 + q^2 = s^2 – 2pq = d^2 + 2pq = 2 [12]
Si pq = 1 [12] alors s^2 = 4 [12] et d^2 = 0 [12]
Si d^2 = 0 [12] alors d est un multiple de 6
Si pq = -1 [12] alors s^2 = 0 [12] et d^2 = 4 [12]
Si s^2 = 0 [12] alors s est un multiple de 6
Selon la valeur de pq modulo 12, on sait donc que soit s soit p est un multiple de 6. -
Si $n=pq=(a+b)(a-b)$ avec $p,q$ deux nombres entiers impairs et on peut supposer $p\geq q$
on peut voir ce qui se passe quand $p=a+b$ et $q=a-b$ et on résout ce système d'équations:
Ainsi, $a=\dfrac{p+q}{2}$ et $b=\dfrac{p-q}{2}$. Or $p\geq q$ et $p,q$ impairs donc $a,b$ sont des entiers naturels.
Il existe une version de l'algorithme de factorisation de Fermat sans test de carré. -
Le problème d'une approche qui divise par $2$ ou $5$ ou $10$ le temps de calcul, c'est que le dixième de l'âge de l'univers, c'est encore trop long.
-
Alors, je crois que la référence à RSA est intéressante.
Sauf erreur, la factorisation d'un produit de deux nombres premiers est un problème réputé NP-complet, c'est-à-dire que si tu le résous en temps polynomial, alors on arrête de faire de la crypto car c'est la fin des haricots. -
Pas tout à fait exact : la classe NP (de même que la classe P) concerne les problèmes de décision dont la réponse est « oui » ou « non ». La factorisation n'est pas éligible pour appartenir à cette classe. Cela dit, un certain nombre de méthodes de cryptographie sont fondées sur la croyance qu'on ne peut pas factoriser efficacement un entier très grand (disons 500 chiffres à ce jour).
-
N'importe quoi, la crypto ne se résume pas à RSA.
-
- Un grand nombre d'algorithmes de crypto repose sur le fait qu'on considère difficile de factoriser de très grands nombres. Un grand nombre d'algorithmes de crypto n'a aucun lien avec la factorisation d'entiers.
- Il existe des algorithmes sous-exponentiels bien plus efficaces que les algos naïfs même améliorés. Les références sur le sujet sont innombrables, je te laisse choisir.
- Le problème de la factorisation est dans la classe NP s'il est posé sous cette forme : on donne un nombre $N$ (l'entier à factoriser) ; existe-t-il un facteur de $N$ qui soit inférieur à $M$ ? Et on retrouve tous les facteurs par dichotomie en faisant varier $M$ comme il faut. -
En effet, quid du logarithme discret ? Quid de knack sack (il y a des versions, me semble-t-il, qui n'ont pas été cassées)?
Et la cryptographie ne se résume pas aux systèmes à clefs publiques de type RSA. (quid de RC4? etc) -
Salut,
@Jer anonyme : la variante décisionnelle de la factorisation est, étant donné $N,X$, déterminer si $N$ possède un facteur premier $p<X$. Connaître la factorisation permet de résoudre ce problème, et un nombre polynomial de résolutions de ce problème permet de trouver la factoriation (dichotomie). Cette variante décisionnelle est dans NP. On ne sait pas si ce problème est NP-complet, mais c'est très peu probable. Comme il n'y a pas de preuve je ne peux que donner des arguments heuristiques :
- les problèmes NP-complets doivent être très combinatoires pour pouvoir encoder les autres problèmes NP, et la factorisation n'est pas un problème assez combinatoire.
- on ne connait d'algorithme sous-exponentiel pour aucun problème NP-complet, et il est tout à fait envisageable qu'il n'en existe pas. Par contre, on connait un algorithme sous-exponentiel pour la factorisation.
Pour défendre Nicolas123, je vous ferais remarquer qu'il n'a pas affirmé que toute la crypto était basée sur la factorisation, mais que si la factorisation est NP-complète et si on sait la résoudre en temps polynomial, alors une bonne partie de la crypto est cassée. C'est en partie vrai, car beaucoup de primitives de crypto asymétrique sont basées sur des problèmes NP. En revanche, les primitives de crypto symétrique ne sont pas trop concernées.
Aurel -
Fin de partie écrivait:
> Va factoriser
> $630000000000000000000000000000000000000000000000000000000000000000000000000\\
000000000000000000019837638200000000000000000000000000000000000000000000000000000000000\\
000000000000000000000000000153722107762559$
> avec l'algo RSA B-)-
En l'occurence ce n'est pas un très bon exemple : ce nombre est très facile à factoriser ;-)
$700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000012398887$
$\times$
$900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000012398057$
C'est pas la taille qui compte :-p
Aurel -
Bonjour,
Bon, on m'a censuré mon jeu de mots vaseux, c'est normal, mais il est vrai qu'avec des lignes LaTeX trop longues, je ne vois pas les chiffres de droite de ces deux facteurs, il faudrait les écrire sur deux lignes chacun.
Cordialement,
Rescassol -
Désolé, sur mon écran je les vois en entier. C'est bon comme ça ?
$700000000000000000000000000000000000000000000000000\\
000000000000000000000000000000000000000000012398887$
$\times$
$900000000000000000000000000000000000000000000000000\\
000000000000000000000000000000000000000000012398057$
Aurel -
Aurelpage:
J'avais bricolé rapidement deux nombres premiers grâce à la fonction nextprime() de PARI-GP.
Je me rendais compte qu'il y avait trop de $0$ dans ce nombre. :-D -
Oui, c'était assez clair comment tu l'avais bricolé.:-D C'était pas une vraie critique mais je trouvais ça marrant et intéressant dans un post où les gens se demandent si on peut factoriser plus facilement certains nombres qui ont certaines propriétés particulières.;-)
Aurel -
Moi je peux factoriser les puissances de 10 super vite.
-
Toutes ? Moi je n'y arrive que si elles n'ont que deux facteurs premiers. ::o
-
aurelpage
Toutes, y compris celles qui ont strictement plus de deux facteurs premiers :-D
[Inutile de recopier le message précédent. AD] -
Si tu insistes Aurelpage je te soumets cet autre nombre qu'il s'agit de factoriser (c'est un produit de deux nombres premiers):
$N=383841783353065792732508955\\117077918003663535276714\\25426669320053927183513\\41294081268958188809\\705567929551635611420\\727993901773985828098651\\89539017341733200\\41630752540982670968\\4349307275988936035894403$
(je l'ai saucissonné en plusieurs "tranches" pour que tout le monde puisse le lire)
J'ai obtenu les facteurs de ce nombre grâce à PARI GP et à:
nextprime(random()*1234789^15)
PS:
Il a une centaine de chiffres cela reste faisable pour un ordinateur personnel. -
Faisable par un ordinateur personnel avec quel algorithme et en combien de temps ?
$18176643201660940603\\
93495329310501194888\\
16431883204085547503\\
850922417948538053355\\
29939701914542288699$
$\times$
$21117308575325459294\\
59225555140184827890\\
23224599217169425051\\
62793786011902515693\\
419624831010635889497$
;-)
Aurel -
Je ne pensais pas que ce serait aussi rapide. Il y a un truc ? :-D
Je peux toujours avoir le dernier mot, bien sûr
-
Oui oui, il y a un truc :-)
Si tu veux chercher, en regardant les mots-clés "substitution de Kronecker" et "factorisation Aurifeuillenne" tu devrais comprendre ce que je fais (ce n'est ni l'un ni l'autre mais les mêmes idées).
Je peux aussi te donner la méthode si tu préfères. ;-)
Aurel -
J'en étais venu à la conclusion que ma génération de nombres premiers était plus que douteuse du point de vue du hasard. :-D
PS:
Je viens de vérifier. C'est vraiment tout pourri si tu ne contrôles pas le seed. :-D
Quand j'ai rechargé PARI GP, il m'a redonné l'un des deux facteurs à ma première tentative de génération. :-D -
Mais... justement, c'est fait pour que tout soit reproductible ! Sinon tout code probabiliste devient impossible à débugger. Le seed est toujours le même à moins que tu le changes manuellement. Mais en l'occurence je n'ai pas exploité ça, ce sont vraiment des nombres faciles à factoriser. ;-)
Aurel -
Un dernier exemple pour la route:
$N=31428068166080317\\
6452331815096\\2681113456672\\91872911537\\438733619139\\074130663209174\\6172585299251\\1434483560204\\71183193668948\\223065292522789266\\9443698124548024939868\\773689852640117322579069\\2032253844680939667087\\4979962567682999970025\\05907811124585116328\\162269171886805122\\4442964571149279056\\19522530374780546\\1427115336914060931$
J'espère que celui-ci va mieux résister :-D
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 164.7K Toutes les catégories
- 46 Collège/Lycée
- 22.1K Algèbre
- 37.4K Analyse
- 6.3K Arithmétique
- 57 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 19 CultureMath
- 50 Enseignement à distance
- 2.9K Fondements et Logique
- 10.6K Géométrie
- 80 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 75 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 334 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 791 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres