Sollte das praktische Quantencomputing Realität werden, frage ich mich, ob es irgendwelche kryptographischen Algorithmen für öffentliche Schlüssel gibt, die auf NP-kompletten Problemen beruhen und nicht auf ganzzahliger Faktorisierung oder diskreten Logarithmen.
Editar:
Bitte lesen Sie den Abschnitt "Quantum computing in computational complexity theory" auf der Wiki-Artikel über Quantencomputer. Es wird darauf hingewiesen, dass die Klasse der Probleme, die Quantencomputer lösen können (BQP), als wesentlich einfacher als NP-komplett gilt.
Bearbeiten 2:
Basierend auf NP-komplett" ist eine schlechte Art auszudrücken, woran ich interessiert bin.
Ich wollte eigentlich nach einem Verschlüsselungsalgorithmus für öffentliche Schlüssel fragen, der die Eigenschaft hat, dass jede Methode zum Brechen der Verschlüsselung auch zum Brechen des zugrunde liegenden NP-kompletten Problems verwendet werden kann. Das heißt, das Brechen der Verschlüsselung beweist P=NP.
