Calcolo delle capacità di fattorizzazione di interi di D-Wave

Question

Calcolo delle capacità di fattorizzazione di interi di D-Wave

#1 da (2 voti)

1

D-Wave ha preso in giro la possibilità di eseguire integer factorization in precedenza, ma se salti a ~ 10: 00 in questa presentazione loro effettivamente sembrano delineare come possono eseguire la fattorizzazione di interi utilizzando la ricottura quantistica e a ~ 12: 10 possono produrre una macchina D-Wave (magari come un ordine speciale NSA) che può contare il numero 2n bit con 2n ² qubits.

Quanti qubit si traduce in questo utilizzando la loro architettura, vale a dire la loro avvertenza sulla "lunghezza della catena" rilevante qui?
C'è un modo semplice per applicarlo a ECC?

I numeri sono seriamente sfocati (raddoppio del qubit annuale e semestrale, limiti di coerenza, ecc.) ma se si tratta semplicemente di aumentare il conteggio dei qubit non elaborati, la durata prevista per le stime della lunghezza della chiave vengono appiattite un po 'per lunghezze RSA più grandi. Se l'ECC è influenzata in modo lineare, la loro durata prevista potrebbe essere la metà di quella delle stime correnti (2030-2060 vs 2050-2100).

Nota: non ripetere semplicemente i reclami generici relativi a D-Wave qui. Ci sono molti forum per quella discussione, questo non è uno di questi.

cryptography rsa quantum-computing ecc

posta Indolering 06.12.2014 - 02:53

fonte

1 risposta

Leggi altre domande sui tag cryptography rsa quantum-computing ecc

Come disattivare il bitlocker per andare su Windows 7 [chiuso] Esiste un modo per simulare la richiesta http di un programma compilato?

score 2 · Answer 1

if you jump to ~10:00 in this presentation they actually appear to outline how they can perform integer factorization using quantum annealing and at ~12:10 they can produce a D-Wave machine (maybe as an NSA special order) that can factor 2n bit number with 2n^2 qubits.

Per prima cosa descrive che puoi descrivere RSA come un problema di ottimizzazione. Ma ciò che si può fare è una vasta classe di problemi, molti dei quali non si ritiene siano calcolabili in modo efficiente sui CQ. Dovrebbe essere semplice codificare i problemi di SAT come questo, e quelli sono NP completi. Sono anche abbastanza sicuro di poter codificare la criptazione simmetrica in questo modo. I risultati di ottimalità attorno all'algoritmo di Grover rendono improbabile l'esistenza di un algoritmo generico in grado di risolvere in modo efficiente tutti i problemi che possono essere codificati in questo modo.

Non menziona alcun RSA / factoring specifico. È teoricamente possibile che la struttura specifica del factoring significhi che l'algoritmo di ottimizzazione risolverà il problema in modo efficiente. Ma il discorso non conteneva alcun segno di prova a riguardo. Inoltre, mancano prove per accelerare oltre il grover o anche il classico computing.