Technologien

Was ist Shor-Algorithmus?

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äuterung

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.

Lösungen

Lösungen

Blogbeiträge

Blogbeiträge

Verwandte Produkte

Verwandte Produkte

Kontakt

Ihre Fragen beantworten wir sehr gerne.

Wie können wir Ihnen helfen?

Sprechen Sie mit einem unserer Spezialisten und erfahren Sie, wie Utimaco Sie unterstützen kann.
Sie haben zwei verschiedene Arten von Downloads ausgewählt, so dass Sie verschiedene Formulare absenden müssen, die Sie über die beiden Tabs auswählen können.

Ihre Download-Sammlung:

    Direkt nach dem Absenden des Formulars erhalten Sie die Links zu den von Ihnen ausgewählten Downloads.

    Ihre Download-Sammlung:

      Für diese Art von Dokumenten muss Ihre E-Mail Adresse verifiziert werden. Sie erhalten die Links für die von Ihnen ausgewählten Downloads per E-Mail, nachdem Sie das unten stehende Formular abgeschickt haben.

      Downloads von Utimaco

      Besuchen Sie unseren Download-Bereich und wählen Sie aus: Broschüren, Datenblätter, White-Papers und vieles mehr. 

      Fast alle können Sie direkt ansehen und speichern (indem Sie auf den Download-Button klicken).

      Für einige Dokumente muss zunächst Ihre E-Mail-Adresse verifiziert werden. Der Button enthält dann ein E-Mail-Symbol.

      Download via e-mail

       

      Der Klick auf einen solchen Button öffnet ein Online-Formular, das Sie bitte ausfüllen und abschicken. Sie können mehrere Downloads dieser Art sammeln und die Links per E-Mail erhalten, indem Sie nur ein Formular für alle gewählten Downloads ausfüllen. Ihre aktuelle Sammlung ist leer.