Ma compréhension est que de nombreux algorithmes cryptographiques clés publiques ces jours-ci dépendent des grands nombres premiers pour constituer les clés, et c'est la difficulté à affirmer le produit de deux nombres premiers qui rend le cryptage difficile à casser. Il est également comprendre que l'une des raisons des raisons qui affactit si des nombres importants sont si difficiles, c'est que la taille des nombres utilisés signifie qu'aucun processeur ne peut fonctionner efficacement sur les chiffres, car nos processeurs de 32 et 64 bits ne sont pas une correspondance. pour 1024, 2048 ou même 4096 bits. Les bibliothèques de mathématiques grandes entière spécialisées doivent être utilisées afin de traiter ces chiffres, et ces bibliothèques sont intrinsèquement lentes puisque une CPU ne peut que contenir (et traiter) de petits morceaux (comme 32 ou 64 bits) à la fois.
SO ...
Pourquoi ne pouvez-vous pas construire une puce personnalisée hautement spécialisée avec des registres de 2048 bits et des circuits arithmétiques géants, bien de la même manière que nous avons mis à l'échelle des processeurs de 8 à 16 à 32 à 32 à 64 bits, construisez-en un beaucoup plus grand ? Cette puce n'aurait pas besoin de la plupart des circuits sur les processeurs conventionnels, après tout, il n'aurait pas besoin de gérer des objets comme une mémoire virtuelle, une multithreading ou des E / S. Il n'aurait même pas besoin d'être un processeur à usage général supportant des instructions stockées. Juste le strict minimum pour effectuer les calculs arithmétiques nécessaires sur des nombres ginormes.
Je ne connais pas beaucoup de choses sur la conception IC, mais je me souviens bien d'apprendre à quel point les portes logiques fonctionnent, comment construire une demi-additionneuse, additionneur complète, puis lier un tas d'additionneurs à faire des arithmétiques multi-bits. Juste à l'échelle. Beaucoup.
Maintenant, je suis assez certain qu'il y a une très bonne raison (ou 17) que ce qui précède ne fonctionnera pas (car sinon, l'une des nombreuses personnes plus intelligentes que je ne l'aurais déjà fait) mais je suis intéressé En sachant pourquoi cela ne fonctionnera pas.
(Remarque: cette question peut avoir besoin d'un peu de travail, car je ne suis même pas sûr que la question a du sens)
6 Réponses :
C'est parce que cette vitesse ne serait que dans O (n), mais la complexité de l'affacturage du nombre est quelque chose comme o (2 ^ n) (par rapport au nombre de bits). Donc, si vous avez fait cet ÜberProcessor et factorisez les chiffres 1000 fois plus rapides, je ne devrais que faire les numéros 10 bits plus grands et nous reviendrons à nouveau.
En fait, la complexité de l'affacturage n'est pas assez exponentielle (O (2 ^ n)); Il y a des algorithmes sous-exponentiels. Mais c'est toujours très lent. Voir en.wikipedia.org/wiki/... pour tous les mathématiques de Gory :-) .
Comme indiqué ci-dessus, le problème principal est simplement le nombre de possibilités que vous devez utiliser pour factoriser un numéro. Cela étant dit, des ordinateurs spécialisés existent pour faire ce genre de chose.
Les progrès réels de ce type de cryptographie sont des améliorations des algorithmes d'affacturage du numéro. Actuellement, l'algorithme général connu le plus rapide est le Numéro général Tamis de champ .
Historiquement, nous semblons être capables de prendre en compte les chiffres deux fois plus grand de chaque décennie. Une partie de celle-ci est une quincaillerie plus rapide et une partie est simplement une meilleure compréhension des mathématiques et de la manière de procéder à l'affacturage.
Que dit @cube, et le fait qu'une unité logique arithmétique géante prendrait plus de temps pour que les signaux logiques se stabilisent et incluent d'autres complications dans la conception numérique. La conception de la logique numérique inclut quelque chose que vous prenez pour acquis dans des logiciels, à savoir que des signaux à travers la logique de combinaison prennent un petit temps petit mais non nul pour se propager et régler. Un multiplicateur de 32x32 doit être conçu avec soin. Un multiplicateur de 1024x1024 ne prendrait pas seulement une énorme quantité de ressources physiques dans une puce, mais elle serait également plus lente qu'un multiplicateur de 32x32 (bien que peut-être plus rapide qu'un multiplicateur de 32x32 computing tous les produits partiels nécessaires pour effectuer un multiplicateur de 1024x1024). De plus, ce n'est pas seulement le multiplicateur qui est le goulot d'étranglement: vous avez des voies de mémoire. Vous devriez passer un tas de temps à rassembler les 1024 bits à partir d'un circuit de mémoire unique de 32 bits de large et stockez les bits de 2048 résultant dans le circuit de mémoire.
Il est presque certain que mieux d'obtenir un groupe de systèmes "conventionnels" 32 bits ou 64 bits fonctionnant en parallèle: vous obtenez le speedUp w / o la complexité de conception matérielle.
Je ne peux pas commenter sur la «EM> Faisabilité d'une approche exactement comme celle que vous avez décrite, mais les gens similaires sont très fréquemment utilisant des FPGA:
Pourquoi n'essayez-vous pas de construire un ordinateur uber-quantum et d'exécuter Algorithme de Shor dessus?
"... Si un ordinateur quantique avec un nombre suffisant de qubits devait être construit, L'algorithme de Shor pourrait être utilisé pour casser des schémas de cryptographie clés publiques tels que le schéma RSA largement utilisé. RSA est basé sur l'hypothèse que l'affacturage des nombres importants est informellement infaisable. Ainsi, comme on le sait, cette hypothèse est valable pour les ordinateurs classiques (non quantum); aucun algorithme classique n'est connu que peut facteur en temps polynomial. Cependant, l'algorithme de Shor montre que L'affacturage est efficace sur un ordinateur quantique, un ordinateur quantique suffisamment important peut donc casser RSA. ... " -wikipedia
Shamir & TROMER Suggérer une approche similaire, en utilisant une sorte de Computing de la grille :
Cet article décrit une nouvelle conception pour un matériel personnalisé mise en œuvre de l'étape de tamisage, qui Réduit [le coût du tamisage, par rapport à Twinkle,] à environ 10 millions de dollars. Le nouvel appareil, appelé twirl, peut être considéré comme une extension de la Dispositif de scintillement. Cependant, contrairement à la scintiller n'a pas de composants optoélectroniques et peut ainsi être fabriqué à l'aide de la technologie VLSI standard sur les gaufrettes de silicium. L'idée sous-jacente est d'utiliser une seule copie de l'entrée pour résoudre de nombreux subproblèmes en parallèle. Puisque le stockage d'entrée domine le coût, si le La surcharge de parallélisation est maintenue basse alors la personne résultante L'accélération est obtenue essentiellement gratuitement. En effet, le Le principal défi réside dans la réalisation de ce parallélisme efficacement tout en permettant un stockage compact de l'entrée. Aborder cela implique des considérations myriades, allant de la théorie des nombres à la technologie VLSI.
Pourquoi quelqu'un a-t-il voté pour fermer cette question?
Stackoverflow.com/faq LOOK SUR "Quel type de question dois-je ne pas demander ici?"
Désolé, je pense que Stackoverflow a commencé avec un bon plan, pour être quelque chose comme des experts-échange, mais mieux, mais il est évolué, il doit grandir. Ces types de méta-discussions devraient être autorisés. Il n'y a presque pas de programmation «Conseils de discussion» pour parler de sujets de programmation de manière ouverte. Personnellement, je pense que cela a besoin d'évoluer avec ses utilisateurs et que les modérateurs doivent cesser d'être comme ceux des nazis sur Wikipedia. En terminez-vous, comment vous pouvez voir le vote fermer des métadonnées, ou est-ce que quelque chose que seul l'auteur de la question voit?