Cálculo de las capacidades de factorización de enteros de D-Wave

Question

Cálculo de las capacidades de factorización de enteros de D-Wave

#1 de CodesInChaos (2 votos)

1

D-Wave ha demostrado la capacidad de realizar factorización de enteros anteriormente, pero si salta a ~ 10: 00 en esta presentación , en realidad parece que se describe cómo pueden realizar la factorización de enteros mediante el recocido cuántico y en ~ 12: 10 pueden producir una máquina D-Wave (quizás como una orden especial de la NSA) que puede factorizar el número de 2n bits con 2n ² qubits.

¿Cuántos qubits se traduce esto al uso de su arquitectura, es decir, es relevante su advertencia de "longitud de cadena"?
¿Existe una forma sencilla de aplicar esto a ECC?

Los números son muy borrosos (duplicación de qubit anual frente a semestral, límites de coherencia, etc.) pero si es simplemente una cuestión de escalar sus conteos de qubit en bruto, entonces la vida útil esperada para estimaciones de longitud de clave se aplanan un poco para longitudes RSA más grandes. Si la ECC se ve afectada de manera lineal, sus vidas esperadas podrían ser la mitad de las estimaciones actuales (2030-2060 vs 2050-2100).

Nota: No repita simplemente las quejas genéricas sobre D-Wave aquí. Hay muchos foros para esa discusión, este no es uno de ellos.

cryptography rsa quantum-computing ecc

pregunta Indolering 06.12.2014 - 02:53

fuente

1 respuesta

Lea otras preguntas en las etiquetas cryptography rsa quantum-computing ecc

¿Se puede detectar ettercap? ¿Hay alguna forma de imitar la solicitud http de un programa compilado?

score 2 · Answer 1

si salta a ~ 10: 00 en esta presentación, en realidad parecen delinear cómo pueden realizar la factorización de enteros utilizando el recocido cuántico y con ~ 12: 10 pueden producir una máquina D-Wave (tal vez como un pedido especial de la NSA) eso puede factorizar el número de 2n bits con 2n ^ 2 qubits.

Primero, él describe que puede describir RSA como un problema de optimización. Pero puede hacer que sea una gran clase de problemas, muchos de los cuales no se consideran computables de manera eficiente en los CC. Debería ser sencillo codificar problemas de SAT como este, y esos son NP completos. También estoy bastante seguro de que puede codificar romper criptografía simétrica de esa manera. Los resultados óptimos en torno al algoritmo de Grover hacen que sea poco probable que exista un algoritmo genérico que pueda resolver de manera eficiente todos los problemas que pueden codificarse de esta manera.

No menciona ningún dato específico de RSA / factoring. En teoría, es posible que la estructura específica de la factorización signifique que el algoritmo de optimización resolvería el problema de manera eficiente. Pero la charla no contenía ningún indicio de evidencia sobre esto. También carece de pruebas de una aceleración más allá de Grover o incluso de la informática clásica.