Kryptografie 05.05.2023, 07:08 Uhr

Innsbrucker Physiker lassen Quantencomputer rückwärts rechnen

Die Faktorierung großer Zahlen stellt herkömmliche Computer vor größere Problemen. Physiker der Universität Innsbruck scheinen hierfür eine Lösung gefunden zu haben, die sich mit Hilfe von Quantencomputern realisieren lässt.

Quantencomputer

Innsbrucker Physiker entwickeln umkehrbare Computer-Gatter für die Faktorisierung großer Zahlen.

Foto: Panthermedia.net/welcomia

Die Faktorisierung großer Zahlen erfordert erhebliche Rechenarbeit, um ihre Bestandteile zu identifizieren. Ein Team von Physikern der Universität Innsbruck unter der Leitung von Professor Wolfgang Lechner hat einen Plan für den Bau eines neuartigen Quantencomputers entwickelt, der das Faktorisierungsproblem lösen kann. Dieses Problem bildet eine Grundlage für moderne Verschlüsselungsmethoden in der Kryptographie. Vereinfacht gesagt kann der Quantencomputer rückwärts rechnen.

Das Problem mit der Zerlegung von Primfaktoren

Die Darstellung bestimmter natürlicher Zahlen als Produkt zweier Primzahlen spielt eine entscheidende Rolle in der Kryptographie. Da das Finden dieser Primfaktoren bei großen Zahlen sehr zeitaufwendig ist, basieren viele Verschlüsselungsverfahren auf dem Prinzip der Primfaktorzerlegung. Schon früh erkannte man das enorme Potenzial von Quantencomputern für die Faktorisierung, doch bisher war es nicht möglich, dieses Potenzial vollständig auszuschöpfen. Nun präsentieren Physiker der Universität Innsbruck ein neues Konzept für einen Quantencomputer, der in der Lage ist, Zahlen durch den Einsatz von Rückwärtsoperationen zu zerlegen.

Top Stellenangebote

Zur Jobbörse
Tagueri AG-Firmenlogo
Teamleitung im Bereich Diagnose (m/w/d) Tagueri AG
Hamburg Zum Job 
Tagueri AG-Firmenlogo
(Junior) Consultant Funktionale Sicherheit (m/w/d) Tagueri AG
Hamburg Zum Job 
Tagueri AG-Firmenlogo
Consultant Systems Engineering (m/w/d) Tagueri AG
Hamburg Zum Job 
Die Autobahn GmbH des Bundes-Firmenlogo
Bauingenieure - Schwerpunkt konstruktiver Ingenieurbau für die Bauwerksprüfung nach DIN 1076 (m/w/d) Die Autobahn GmbH des Bundes
Hamburg Zum Job 
Funkwerk AG-Firmenlogo
Techniker / Ingenieur im Engineering Vertrieb (m/w/d) Funkwerk AG
deutschlandweit Zum Job 
ITW Fastener Products GmbH-Firmenlogo
Technische:r Vertriebsingenieur:in für VW ITW Fastener Products GmbH
Creglingen-Münster Zum Job 
Framatome GmbH-Firmenlogo
Senior Project Quality & OPEX Manager (m/w/d) Framatome GmbH
Erlangen Zum Job 
Rheinmetall Electronics GmbH-Firmenlogo
Elektronikentwickler (m/w/d) Rheinmetall Electronics GmbH
Rheinmetall Electronics GmbH-Firmenlogo
Projektingenieur Kältemittelverdichter (m/w/d) Rheinmetall Electronics GmbH
Forschungszentrum Jülich GmbH-Firmenlogo
Ingenieur für Gebäudeausrüstung / Versorgungstechnik (w/m/d) Forschungszentrum Jülich GmbH
Jülich bei Köln Zum Job 
Diehl Aerospace GmbH-Firmenlogo
Ingenieur / Entwicklungsingenieur (m/w/d) Avionik (System) Diehl Aerospace GmbH
Nürnberg, Überlingen, Frankfurt am Main, Rostock Zum Job 
Rheinmetall Electronics GmbH-Firmenlogo
Projektmanager technische Entwicklungsaktivitäten (m/w/d) Rheinmetall Electronics GmbH
Neckarsulm Zum Job 
Stadtwerke Verkehrsgesellschaft Frankfurt am Main mbH-Firmenlogo
Teamleitung Haltestellen und Stationen (d/m/w) Stadtwerke Verkehrsgesellschaft Frankfurt am Main mbH
Frankfurt am Main Zum Job 
Lahnpaper GmbH-Firmenlogo
Leitung Entwicklungslabor (m/w/d) Lahnpaper GmbH
Lahnstein Zum Job 
Energieversorgung Halle Netz GmbH-Firmenlogo
Projektingenieur - Fernsteuerung Energienetze (m/w/d) Energieversorgung Halle Netz GmbH
Halle (Saale) Zum Job 
Riedel Bau-Firmenlogo
Energieberater / Auditor (m/w/d) Riedel Bau
Schweinfurt Zum Job 
SWM Services GmbH-Firmenlogo
Projektingenieur*in im digitalen Messwesen (m/w/d) SWM Services GmbH
München Zum Job 
Die Autobahn GmbH des Bundes-Firmenlogo
Ingenieur (w/m/d) Elektro- / Kommunikationstechnik Die Autobahn GmbH des Bundes
Frankfurt am Main Zum Job 
RENOLIT SE-Firmenlogo
Ingenieur / Techniker (m/w/d) für Automatisierungstechnik RENOLIT SE
Frankenthal Zum Job 
BREMER Bremen GmbH-Firmenlogo
Kalkulator (m/w/d) BREMER Bremen GmbH

Die Primfaktorzerlegung stellt für klassische Computer eine Herausforderung dar, da sie auf irreversiblen Prozessen beruhen. Algorithmen haben in klassischen Computern eine feste Richtung und können nicht einfach rückwärts ablaufen, erklärte Wolfgang Lechner. Daher ist die Multiplikation zweier Zahlen, selbst wenn sie groß sind, für einen klassischen Computer einfach durchzuführen, während die Zerlegung großer Zahlen eine deutlich größere Herausforderung darstellt.

Selbst einfache Rechenaufgaben lassen sich nicht rückwärts rechnen

Nimmt man die Multiplikation 2*2=4, so kann man diese Operation nicht einfach umgekehrt ablaufen lassen, weil 4 könnte 2*2 sein, aber genauso 1*4 oder 4*1“, erklärt Wolfgang Lechner, Professor für Theoretische Physik an der Universität Innsbruck. Wenn es jedoch möglich wäre, dies zu erreichen, hätte man die Möglichkeit, große Zahlen zu faktorisieren und somit in ihre Primfaktoren zu zerlegen. Dies stellt einen entscheidenden Grundpfeiler in der Kryptographie dar.

Im Jahr 1994 entwickelte der amerikanische Mathematiker Peter Shor einen Algorithmus, der mithilfe eines hypothetischen Quantencomputers die Primfaktoren von Zahlen wesentlich schneller finden könnte als ein herkömmlicher Computer. Zu dieser Zeit existierte jedoch noch kein funktionsfähiger Quantencomputer. Der sogenannte Shor-Algorithmus erfordert allerdings eine beträchtliche Anzahl von Quantenbits (Qubits), insbesondere bei großen Zahlen. Qubits sind die grundlegenden Informationseinheiten eines Quantencomputers und können mit verschiedenen physikalischen Systemen realisiert werden, darunter Ionen, Atome, Photonen oder supraleitende Schaltkreise.

Nach wie vor ist es jedoch schwierig, eine zuverlässige Kontrolle über eine große Anzahl von Qubits zu erreichen und sie mithilfe des quantenphysikalischen Phänomens der Verschränkung zu einer kohärenten Einheit zusammenzuführen. Aus diesem Grund verfügen aktuelle Quantencomputer nur über eine begrenzte Anzahl von Quantenbits und sind selbst mit dem Shor-Algorithmus noch nicht in der Lage, Verschlüsselungsverfahren auf der Basis großer Zahlen zu entschlüsseln.

Martin Lanthaler (li.) und Wolfgang Lechner (re.) vom Institut für Theoretische Physik der Universität Innsbruck.

Martin Lanthaler (li.) und Wolfgang Lechner (re.) vom Institut für Theoretische Physik der Universität Innsbruck.

Foto: ParityQC

Physiker entwickeln neue Methode

Martin Lanthaler, Ben Niehoff und Wolfgang Lechner vom Institut für Theoretische Physik der Universität Innsbruck haben nun eine Alternative zum Shor-Algorithmus entwickelt. Ihre Idee haben Sie im Fachjournal „Natur Communications Physics“ veröffentlicht. Wolfgang Lechner erläutert dazu, dass die Idee dahinter besteht, die Multiplikation umzukehren. Dies basiert auf dem quantenphysikalischen Phänomen der „Superposition“, das in der alltäglichen Erfahrung nicht nachvollziehbar ist. Während ein klassisches Bit im herkömmlichen Computer nur zwei Zustände (0 oder 1) haben kann, kann ein Qubit mehrere Zustände gleichzeitig annehmen. „Konkret bedeutet das, dass ich eine Quantenmultiplikation baue und diese dann umdrehe. Wenn ich dann 4 eingebe, bekomme ich eine Superposition von allen Möglichkeiten, die zu 4 führen, also 2×2, 1×4 und 4×1“, so Lechner.

Basierend auf der an der Universität Innsbruck entwickelten Parity-Architektur, die mittlerweile von ParityQC kommerziell angeboten wird, benötigt ein solcher Quantencomputer laut dem Physiker „viel weniger Qubits als für den fehlerkorrigierten Shor-Algorithmus“. Um beispielsweise einen gängigen RSA-Schlüssel mit einer Länge von 2048 Bit zu knacken, würde der Shor-Algorithmus Milliarden von Qubits und eine unglaublich große Anzahl von Quanten-Gattern (10 hoch 21) erfordern. „Ein nach unserem Bauplan konzipierter Quantencomputer benötigt dagegen nur 14 Millionen Qubits und keine Quanten-Gatter, sondern läuft analog“, erklärte Lechner. Die neue Architektur sei gut skalierbar, da alle benötigten Grundbausteine gleich aussehen und parallel betrieben werden können.

Quantenverfahren beschleunigen den Suchprozess

„Kern unserer Arbeit ist die Codierung der Grundbausteine des Multiplizier-Schaltkreises, konkret von UND-Gatter, Halb-und Volladdierer mit der Parity-Architektur als Grundzustandsproblem auf einem Ensemble von wechselwirkenden Spins“, erklärt Martin Lanthaler. Durch die Codierung ist es möglich, den gesamten Schaltkreis aus wiederholenden Subsystemen aufzubauen, die auf einem zweidimensionalen Raster angeordnet werden können. Zusätzlich können durch die Reihung mehrerer solcher Subsysteme größere Probleminstanzen realisiert werden.

Im Gegensatz zur klassischen Brute-Force-Methode, bei der alle möglichen Faktoren ausprobiert werden, können Quantenverfahren den Suchprozess beschleunigen. Um den Grundzustand zu finden und ein Optimierungsproblem zu lösen, ist es nicht erforderlich, die gesamte Energielandschaft zu durchsuchen. Stattdessen können tieferliegende Täler durch das Phänomen des „Tunnelns“ erreicht werden.

Das Konzept hat nach Ansicht der Innsbrucker Physiker noch weitere Vorteile, so lasse sich zum Beispiel die Architektur mit allen Quantensystemen realisieren. Dazu gehören beispielsweise Atome oder supraleitende Schaltkreise. „Zudem brauchen wir kein Pre- und kein Postprocessing – bei unserem Computer sind sowohl der Input als auch der Output klassische Daten“, so Lechner. Beim herkömmlichen Quantencomputer sei die Aufbereitung der Daten und das Auslesen der Ergebnisse hingegen sehr aufwendig.

Ein Beitrag von:

  • Dominik Hochwarth

    Redakteur beim VDI Verlag. Nach dem Studium absolvierte er eine Ausbildung zum Online-Redakteur, es folgten ein Volontariat und jeweils 10 Jahre als Webtexter für eine Internetagentur und einen Onlineshop. Seit September 2022 schreibt er für ingenieur.de.

Themen im Artikel

Zu unseren Newslettern anmelden

Das Wichtigste immer im Blick: Mit unseren beiden Newslettern verpassen Sie keine News mehr aus der schönen neuen Technikwelt und erhalten Karrieretipps rund um Jobsuche & Bewerbung. Sie begeistert ein Thema mehr als das andere? Dann wählen Sie einfach Ihren kostenfreien Favoriten.