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
WISAG Elektrotechnik Berlin-Brandenburg GmbH & Co. KG-Firmenlogo
Elektroingenieur | Meister als Planer (m/w/d) für Großanlagen WISAG Elektrotechnik Berlin-Brandenburg GmbH & Co. KG
HOCHBAHN U5 Projekt GmbH-Firmenlogo
Bauingenieur*in als Teilprojektleiter*in Planung U5 HOCHBAHN U5 Projekt GmbH
Hamburg Zum Job 
enercity AG-Firmenlogo
Bachelor / Master Elektrotechnik als Koordinator:in Metering Strom enercity AG
Hannover Zum Job 
James Hardie Europe GmbH-Firmenlogo
Prozessingenieur (m/w/d) James Hardie Europe GmbH
Neudenau/Siglingen Zum Job 
KANZAN Spezialpapiere GmbH-Firmenlogo
Technischer Projektplaner / Ingenieur / Techniker (m/w/d) in der Papierindustrie KANZAN Spezialpapiere GmbH
Die Autobahn GmbH des Bundes-Firmenlogo
Ingenieur (w/m/d) für Bauunterhalt und Projektleitung Die Autobahn GmbH des Bundes
Nürnberg Zum Job 
Hamamatsu Photonics-Firmenlogo
Vertriebsingenieur (m/w/d) für den Bereich Spektrometer und Mikroskopie Hamamatsu Photonics
Herrsching am Ammersee Zum Job 
HOCHBAHN U5 Projekt GmbH-Firmenlogo
Projektingenieur*in Leit- und Sicherungstechnik U5 HOCHBAHN U5 Projekt GmbH
Hamburg Zum Job 
BASF Coatings GmbH-Firmenlogo
Werkstudent:in im Bereich technische Dokumentation (w/m/d) BASF Coatings GmbH
Münster Zum Job 
Albert Handtmann Metallgusswerk GmbH & Co. KG-Firmenlogo
Leiter Entwicklung und Konstruktion / Engineering Manager (m/w/d) Albert Handtmann Metallgusswerk GmbH & Co. KG
Biberach Zum Job 
BASF SE-Firmenlogo
Praktikum Prozessmanagement (m/w/d) BASF SE
Ludwigshafen Zum Job 
BASF Coatings GmbH-Firmenlogo
Digital Rotational Programm - Digital Commerce (m/w/d) BASF Coatings GmbH
Münster, Ludwigshafen Zum Job 
LTS Lohmann Therapie-Systeme AG-Firmenlogo
IP Manager (m/w/d) LTS Lohmann Therapie-Systeme AG
Andernach Zum Job 
SHS - Stahl-Holding-Saar GmbH & Co. KGaA-Firmenlogo
Projektleiter Verfahrenstechnik (m/w/d) SHS - Stahl-Holding-Saar GmbH & Co. KGaA
Dillingen/Saar Zum Job 
Sweco GmbH-Firmenlogo
Projektingenieur Elektrotechnik (m/w/x) Sweco GmbH
LEONHARD WEISS GmbH & Co. KG-Firmenlogo
Kalkulator Schlüsselfertigbau (m/w/d) LEONHARD WEISS GmbH & Co. KG
Hamburg Zum Job 
Technische Universität Wien-Firmenlogo
Universitätsprofessor_in für das Fachgebiet Stahlbeton- und Massivbau Technische Universität Wien
Wien (Österreich) Zum Job 
Technische Universität Dresden-Firmenlogo
Research Associate (m/f/x) Technische Universität Dresden
Dresden Zum Job 
Stadtwerke Heidelberg Netze GmbH-Firmenlogo
Ingenieur (m/w/i) Netzplanung / Netzberechnung Strom Stadtwerke Heidelberg Netze GmbH
Heidelberg Zum Job 
Herzog GmbH-Firmenlogo
Technischer Projektingenieur (m/w/d) Herzog GmbH
Schramberg Zum Job 

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

    Content-Manager beim VDI Verlag. Nach einem Bauingenieurstudium und einer Weiterbildung zum Online-Redakteur, Volontariat und 20 Jahren als Webtexter für eine Internetagentur und einen Onlineshop, landete er bei ingenieur.de. Er schreibt hauptsächlich über Technik und Forschung.

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.