Definition: 1994 entwickelte Peter Shor, Professor für Mathematik am MIT, einen Quantenalgorithmus zur Erzeugung von Primfaktoren großer Zahlen, der wesentlich effizienter ist als klassische Computer. Der Shor-Algorithmus ist ein Quantencomputer-Algorithmus, der Primfaktoren einer ganzen Zahl in Polynomialzeit lösen kann. Er ermöglicht die Faktorisierung von Primzahlen in O(logN ^3) Laufzeit und O(logN) Speicherplatz.
Erläuterungen zum Shor-Algorithmus
Primfaktoren zu finden, ist seit Jahrhunderten ein schwieriges Problem. Das Faktorisierungsproblem ist eines der ungelösten Probleme der Informatik. Es kann einige Sekunden dauern, die Primfaktoren von 51 zu finden, aber es kann Jahre dauern, die Primfaktoren einer 100-stelligen Zahl zu finden, wenn mehrere herkömmliche Computer parallel faktorisieren.
Viele Verschlüsselungsalgorithmen, die für die Sicherheit von Kreditkarten und ähnlichen Finanztransaktionen verwendet werden, nutzen dieses „Faktorisierungsproblem“ aus. Es wird angenommen, dass, wenn dieses Factoring-Problem gelöst werden kann, auch das Knacken eines Verschlüsselungsalgorithmus wie RSA möglich ist. Ein einzelner Quantencomputer könnte dieses Problem leicht lösen, indem er den Shor-Algorithmus ausführt.
Der Shor-Algorithmus kann jedoch nur auf Computern mit einer großen Anzahl von Quantenbits funktionieren. Es wurden viele Versuche unternommen, den Shor-Algorithmus in verschiedenen Quantensystemen zu implementieren, allerdings ist es keinem gelungen, ihn mit wenigen Quantenbits annähernd zu implementieren. Der Shor-Algorithmus gilt als einer der bisher anspruchsvollsten Algorithmen der Quanteninformatik. Der Algorithmus kann auf einem Quantencomputer umgesetzt werden.
Viele Verschlüsselungsschemata gehen davon aus, dass die Faktorisierung großer Zahlen nicht in Polynomialzeit möglich ist. Wäre es möglich, könnten Verschlüsselungsalgorithmen wie RSA gebrochen werden. Dies führt zu neuen Konzepten wie der Post-Quanten-Kryptografie und dem Quanten-Hacking.
Der Shor-Algorithmus benötigt 10243 Operationen, um eine 1024-Bit-Zahl zu faktorisieren. Ein Quantencomputer mit einer Rechenleistung von 100 MIPS kann jedoch eine 1024-Bit-Zahl in Sekunden faktorisieren. Um einen einzigen verschränkten Zustand zu erreichen, werden 2 Register mit 2048 bzw. 1024 Qubits verwendet, die kohärent arbeiten.
Probleme mit dem Shor-Algorithmus
- Der Shor-Algorithmus ist nicht die beste Methode auf klassischen Computern. Die Algorithmen wie Quadratisches Sieb, Lenstra elliptische Kurvenfaktorisierung und Zahlkörpersieb schneiden bei diesem Problem auf herkömmlichen Computern besser ab.
- Trotz der unglaublich schnellen Leistung des Shor-Algorithmus ist die größte Zahl, die ein Quantencomputer mit dem Shor-Algorithmus faktorisiert hat 21.
Anwendungen des Shor-Algorithmus mit einem Quantencomputer
- Der Shor-Algorithmus kann Primfaktoren sehr großer Zahlen auf einem Quantencomputer berechnen.
- Der Shor-Algorithmus kann möglicherweise zum Knacken von RSA und anderen sicheren Datenformen verwendet werden
- Der Shor-Algorithmus kann das Problem lösen, die Periode einer Funktion zu finden.
Utimaco ist in der Lage, quantenresistente Lösungen anzubieten, die es Unternehmen ermöglichen, ihre Systeme gegen Angriffe auf Quantencomputer zu verteidigen, indem sie viel Zeit und Expertise in die Post-Quanten-Kryptografie investieren.
