J'ai récemment lu sur l'utilisation générale des principaux facteurs au sein de la cryptographie. Partout où j'ai lu, il indique qu'il n'y a pas d'algorithme "publié" qui fonctionne en temps polynomial (par opposition à une période exponentielle), pour trouver les facteurs primaires d'une clé.
Si un algorithme a été découvert ou publié qui fonctionnait en polynôme, alors comment cet impact dans l'environnement de l'informatique mondial réel opposé au monde de la théorie et de l'informatique. Compte tenu de la mesure où nous dépendons de la cryptographie, le serait soudainement arrêté.
Avec cela à l'esprit si p = np est vrai, qu'est-ce que nous devrions arriver, combien cela dépendons-nous du fait qu'il est encore utile.
Je suis un débutant alors s'il vous plaît pardonnez toutes les erreurs dans ma question, mais je pense que vous obtiendrez mon gist général.
6 Réponses :
Dans cet esprit, si n = np est vrai, ils nous le diront-ils jamais?
qui sont " ils "? Si c'était vrai, nous saurais. Les informaticiens? C'est nous. Les cryptographes et les mathématiciens? Les professionnels? Les experts? Des gens comme nous. Utilisateurs d'Internet, même de débordement de pile.
Nous n'aurions pas besoin d'être dit. Nous allions dire .
La science et la recherche n'est pas faite derrière les portes fermées. Si quelqu'un découvre que p = np, cela ne pouvait pas être gardé secret, simplement à cause de la publication de la recherche. En principe, tout le monde a accès à une telle recherche.
Les bons gars, qui l'ont découvert, comme opuit aux terroristes, à la fin des types du monde. Je comprends ce que tu veux dire, je ne pouvais pas penser à une meilleure façon de l'exprimer. Si N = NP s'est avéré vrai, il serait bien de penser que cela se prononce de manière significative, concernera la mesure dans laquelle la sécurité en dépend (en ce moment).
+1: Qui sont "ils" quand même? Je me suis demandé à ce sujet depuis longtemps.
C'est l'idéal scientifique, mais ce n'est pas la seule façon de faire des recherches. Une méthode ou une preuve pourrait toujours travailler même si elle n'est pas publiée dans des revues examinées par des pairs. Bien qu'il y aura relativement peu d'organisations avec les ressources pour faire de sérieuses recherches à huis clos, je suis à peu près sûr que la crypto est une zone de nombreuses personnes qui sont intéressées.
La NSA effectue très certainement des recherches à huis clos, et il n'est pas du tout clair qu'ils publieraient un tel résultat. Je suis sûr que cela fuirait finalement, mais vous ne savez jamais =)
La NSA engage beaucoup de bons mathématiciens à travailler sur Crypto et semble rester devant le monde universitaire sur des questions cryptographiques (bien que les seules personnes qui ne connaissent pas vraiment ne parlent pas). Ce serait beaucoup plus grand que la crypto. Si la NSA pouvait le balancer, les universitaires ne pouvaient pas être loin derrière.
@Stephen, David: Même la NSA utilise des RFP pour concevoir leurs algorithmes de cryptographie, car ils se rendent compte qu'ils ne peuvent pas garder tous les esprits brillants derrière les portes à huis clos. Alors oui, l'armée effectue des recherches derrière des portes à huis clos, de même que de nombreuses grandes entreprises. Mais je crois que tout le travail vraiment révolutionnaire ne peut être gardé secret. En ce qui concerne l'affirmation selon laquelle la NSA est "devant" de la recherche publique, je doute plutôt. Leurs ressources, bien que vastes, sont simplement trop limitées pour concurrencer «fondamentalement tout le reste», sauf sur de très petits problèmes.
Une autre chose à noter est la facilité de fuite d'un algorithme contre d'autres idées de complot. Si, par exemple, l'armée avait capturé un étranger, il n'ya presque pas de preuves qui vont convaincre tout le monde (même des preuves physiques vont être douteuses). D'autre part, si une personne a un algorithme pour prendre un numéro en temps polynomial, aucune autre preuve n'est nécessaire - elle fonctionne, ou cela ne le fait pas.
"Cela fonctionne soit, ce n'est pas" - bien que vous ayez besoin de la preuve que c'est polnomial, ainsi que l'algorithme. Par exemple, je peux facilement vous donner un algorithme qui fact les numéros de temps polynomial si et seulement si un algorithme existe, ce qui le fait. Mais si même cet algorithme fonctionne dans du temps polynomial, la preuve qu'elle est formidable. Gardant à l'esprit qu'il y a des gens qui croient que vous pouvez carré le cercle, convaincant tout le monde est assez inaccessible ;-)
Si un algorithme vraiment efficace pour l'affacturage des nombres composites a été découvert, je pense que le plus gros impact immédiat serait sur le commerce électronique. Plus précisément, il serait arrêté jusqu'à ce qu'une forme de cryptage soit développée qui ne s'appuie pas sur l'affacturage étant une fonction à sens unique.
Il y a eu beaucoup de recherches sur la cryptographie dans le secteur privé depuis quatre dernières décennies. C'était un gros changement de l'ère précédente, où Crypto était en grande partie dans la compétence des agences gouvernementales militaire et secrète. Ces agences secrètes ont définitivement essayé de résister à ce changement, mais une fois que la connaissance est découverte, il est très difficile de le garder sous les enveloppements. Dans cet esprit, je ne pense pas qu'une solution au problème P = NP resterait un secret pour longtemps, malgré toutes les ramifications que cela pourrait avoir dans cette zone. Les avantages potentiels seraient dans une gamme beaucoup plus large d'applications.
Incidemment, il y a eu une autre Recherche dans cryptographie quantique , qui
repose sur les fondements de la mécanique quantique, contrairement à la cryptographie principale traditionnelle de la clé publique qui repose sur la difficulté de calcul de certaines fonctions mathématiques et ne peut fournir aucune indication d'écoute ou de garantie de sécurité clé.
Le Premier réseau pratique Utiliser cette technologie est allé en ligne en 2008 .
Merci, c'est ce que je suis après, combien le monde réel dépend-il de cela et que pourrait-il arriver, je ne suis pas un complot de complot, mais il y a sûrement ceux qui pouvaient rajerment havock si un tel alogthme est trouvé.
Vous ne parlez que sur la partie de la clé publique (PKI) de Crypto. Les algorithmes de cryptage symétriques (par exemple, AES) n'utilisent pas de nombres premiers. Mais il sont quelques algorithmes asymétriques alternatifs, ils ne sont tout simplement pas commercialement populaires.
"Cela serrait à une halte jusqu'à ce qu'une forme de cryptage soit développée qui ne s'appuie pas sur l'affacturage étant une fonction à sens unique". ECC, par exemple. En supposant que cette percée de factorisation ne résout pas également le problème du logarithme discret.
-1: il ne serrerait pas d'arrêter; Il existe des méthodes de crypto existantes qui ne reposent pas sur la difficulté de la factorisation ni du journal discrète (ce qui serait presque certainement cassé si la factorisation était, bien que je ne connaisse pas une réduction explicite).
Voici un article sur du lien:
Beaucoup se concentrent sur le négatif, que si p
= NP puis la cryptographie cline publique devient impossible. Vrai, mais ce que nous
gagnera de p = np fera la
Internet entier ressemble à une note de bas de page dans
Histoire.
depuis la totalité de l'optimisation NP-complète
les problèmes deviennent faciles, tout va
être beaucoup plus efficace. Transport
de toutes les formes seront programmées
de manière optimale pour déplacer les gens et les biens
autour plus rapide et moins cher.
Les fabricants peuvent améliorer leur
la production pour augmenter la vitesse et
créer moins de déchets. Et je suis juste
gratter la surface.
Compte tenu de cette citation, je suis sûr que ils disent au monde.
Je pense qu'il y avait des chercheurs au Canada (?) qui avaient de la chance de faire de la chance en affachant de grands nombres avec des GPU (ou des grappes de GPU). Cela ne signifie pas qu'ils ont été pris en compte en temps polynomial, mais l'architecture de la puce était plus favorable à la factorisation. p = np de l'ACM: http://cacm.acm.org/magazines/2009/9/38904-Le-status-f-the-p-versus-np-problème / Fulltext
Je n'ai pas connu que d'autres personnes se sont concentrées sur cela, c'est juste une observation que j'ai faite, je tente juste de savoir combien nous dépendons réellement du fait que n = np est imprégné.
Cela dépend de qui le découvre.
NSA et d'autres organisations qui recherchent la cryptographie de la recherche de parrainage de l'État, contrairement à l'affirmation de Konrad, font la recherche et la science derrière des portes fermées et des armes à feu. Et ils ont "scoopé" des chercheurs académiques publiés sur certaines découvertes importantes. Enfin, ils ont des antécédents de retenue des avancées cryptanalytiques pendant des années après leur découverte de manière indépendante par des chercheurs universitaires.
Je ne suis pas grand dans les théories du complot. Mais je serais très surpris que beaucoup d'argent "noir" n'aient pas été dépensé par les gouvernements sur le problème de la factorisation. Et si des résultats sont obtenus, ils seraient gardés secrets. Beaucoup de critiques ont été nivelées dans des agences de l'USA pour ne pas être coordonnées les unes avec les autres pour éviter le terrorisme. Il serait peut-être que notifier que le FBI des informations recueillies par la NSA révélerait «trop» sur les capacités de la NSA.
Vous trouverez peut-être la première question posée à Bruce Schneier dans Cette interview intéressante. Le résultat est que la NSA aura toujours un avantage sur le monde universitaire, mais cette marge se rétrécit.
Pour ce qu'il vaut, la NSA recommande l'utilisation de l'accord de clé de courbe elliptique Diffie-Hellman, pas de chiffrement RSA. Est-ce qu'ils aiment les plus petites clés? Est-ce qu'ils envisagent d'être en avant à l'informatique quantique? Ou ...?
+1 en fait. Mais je me tiens à ma remarque dans les commentaires ci-dessous. ;-)
Je suis d'accord avec le principe que garder les vérités mathématiques cachées longtemps n'est pas possible. Mais pendant que cela dure, un secret comme celui-ci est une carte précieuse que tout État jouerait soigneusement.
IIRC, l'algorithme de courbe elliptique publié par la NSA a été découverte de quelque chose qui pourrait être une porte arrière, alors peut-être que c'est pourquoi ils poussaient son utilisation? Schneier.com/essay-198.html
Ce n'est pas une faille dans l'accord clé CE, mais c'est une faille dans la RNG recommandée par la NSA. Mais c'est une bonne illustration; Les deux que la NSA pourrait dissimuler de manière sélective ou révéler des résultats cryptanalytiques et que les universités découvrent souvent de manière indépendante le même résultat dans quelques années.
P = NP a beaucoup de conséquences au-delà de la cryptographie. Si prouvé, nous saurions. C'est l'une des plus grandes, sinon la plus grande question ouverte en informatique aujourd'hui.
"Nous saurions?" Comment? Nous devrions être informés de quiconque le découvre. Et certaines des personnes qui sont les plus susceptibles de découvrir ont des raisons de ne pas la divulguer immédiatement.
comme une note latérale, si vous entrez dans le domaine de l'informatique quantique, vous pouvez prendre en compte du temps polynomial. voir les notes de Rob Pike de sa conversation sur l'informatique quantique, page 25 , également appelé Algorithme de Shor .
Je pense que les ordinateurs quantiques feront la question de n = np obsolète avant que quiconque prouve p = np ou ne le prouve pas.
@gmatt: Nope; Il y a beaucoup de choses NP utiles qui, apparemment, des ordinateurs quantiques ne pourront pas faire. De plus, il devient très difficile de faire des ordinateurs quantiques avec beaucoup de qubits et, tandis que la factorisation était une réalisation impressionnante compte tenu de tout ce qu'elle peut être facilement dupliqué avec des ordinateurs classiques modernes. Je ne sais pas si les ordinateurs quantiques seront jamais utiles.
@David: vraiment? C'est surprenant pour moi, je pensais que la classe de problèmes NP, et P est telle que si vous pouvez résoudre tout problème dans cette classe, tous les autres problèmes peuvent être résolus à l'aide du même algorithme.
GMATT: L'affacturage est dans NP, mais aussi CO-NP. C'est un problème étrange, voici la page wiki: en.wikipedia.org/wiki/integer_factorization
@Dog: Si vous résolvez un problème complet de NP en polynôme, vous les avez tous résolus. Mais les ordinateurs quantiques ne sont pas connus ou censés être capables de résoudre aucun problème complet NP-complet. Recherchez la complexité Classe BQP pour plus d'informations sur ce qui pourrait être résolu efficacement. L'algorithme de Shor et l'algorithme de grofle sont les plus connus.
Gardez à l'esprit que l'affacturage n'est pas connu d'être (et est conjecturé de ne pas être) NP-complet, démontrant ainsi un P algorithme de l'affacturage pas implique p = np. Vraisemblablement, nous pourrions changer la base de nos algorithmes de cryptage vers un problème complet de NP-complet.
Devrait être un wiki communautaire. Peut-être aussi un meilleur candidat à Mathoverflow.net
Comment peut-il le déplacer, êtes-vous capable de le faire ou de me faire savoir comment, merci Chris.
Les questions pourraient être migrées vers Serverfault ou SuperUser d'ici. Pour Mathoverflow.net, je pense que vous devrez vous inscrire à un compte et poster la question là-bas (je ne pense pas que cela soit affilié à ce site).
Semble être un mélange de théorie des mathématiques et du complot. (En général, aucune découverte mathématique ne peut être maintenue à des enveloppements très longtemps, il serait donc préférable de supprimer la théorie du complot.)
Je viens de jeter un coup d'œil à Mathoverflow.net. Je ne pense pas que cette question irait mieux là-bas. Ils semblent favoriser les choses difficiles. BTW, vous pouvez poser cette question n'importe où que vous avez un compte. Il pourrait être déplacé là-bas par suffisamment de personnes avec un représentant 3K + ou un modérateur.
@David Thornley: Nous ne devons pas laisser les masses savoir sur l'irrationalité de la racine carrée de deux!
@David Thornley: True, à la deuxième pensée, je suis d'accord sur le "probablement n'appartiennent pas à la déclaration de Mathoverflow.net".
Je dois dire que je ne comprends pas comment il s'agit de non-programmation. La question revient à "quels problèmes algorithmiques réels seraient affectés si p = np" qui semble être une question parfaitement raisonnable.
Cela appartient carrément en informatique.