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.
You have selected two different types of downloads, so you need to submit different forms which you can select via the two tabs.

Your download request(s):

    By submitting below form you will receive links for your selected downloads.

    Your download request(s):

      For this type of documents, your e-mail address needs to be verified. You will receive the links for your selected downloads via e-mail after submitting below form.

      About Utimaco's Downloads

      Visit our Downloads section and select from resources such as brochures, data sheets, white papers and much more. You can view and save almost all of them directly (by clicking the download button).

      For some documents, your e-mail address needs to be verified. The button contains an e-mail icon.

      Download via e-mail

       

      A click on such a button opens an online form which we kindly ask you to fill and submit. You can collect several downloads of this type and receive the links via e-mail by simply submitting one form for all of them. Your current collection is empty.