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
Jakob Mooser GmbH / Mooser EMC Technik GmbH-Firmenlogo
Prüfingenieur / Prüftechniker (m/w/d) Jakob Mooser GmbH / Mooser EMC Technik GmbH
GASCADE Gastransport GmbH-Firmenlogo
Ingenieur mit Schwerpunkt Maschinenbau / Elektrotechnik / Verfahrenstechnik - als Referent Gasdisposition (m/w/d) GASCADE Gastransport GmbH
Bunge Deutschland GmbH-Firmenlogo
Projektingenieur (m/w/d) Bunge Deutschland GmbH
Mannheim Zum Job 
Berliner Wasserbetriebe-Firmenlogo
Facheinkäufer:in (w/m/d) Berliner Wasserbetriebe
Berliner Wasserbetriebe-Firmenlogo
Facheinkäufer:in (w/m/d) Berliner Wasserbetriebe
OSRAM GmbH-Firmenlogo
Head of Strategy & Marketing - Entertainment & Industry Lamps (ENI) (d/m/f) OSRAM GmbH
München Zum Job 
ams Sensors Germany GmbH-Firmenlogo
Product Manager Automotive - Driver IC (d/m/f) ams Sensors Germany GmbH
Garching bei München Zum Job 
OSRAM GmbH-Firmenlogo
Key Account Manager*in (d/m/w) OSRAM GmbH
München Zum Job 
ARRK Engineering GmbH-Firmenlogo
IT Consultant Digitalisierung / Webentwicklung (m/w/d) ARRK Engineering GmbH
München Zum Job 
TÜV Technische Überwachung Hessen GmbH-Firmenlogo
Ausbildung zum Prüfingenieur bzw. Sachverständigen (m/w/d) für den Tätigkeitsbereich Fahrzeugprüfung und Fahrerlaubnisprüfung TÜV Technische Überwachung Hessen GmbH
Frankfurt am Main Zum Job 
ARRK Engineering GmbH-Firmenlogo
Analyst im Bereich Fahrerassistenz / Autonomes Fahren (m/w/d) ARRK Engineering GmbH
München Zum Job 
ARRK Engineering GmbH-Firmenlogo
Technisches Projektmanagement - Entwicklung von automotive Anzeigesystemen (m/w/d) ARRK Engineering GmbH
München Zum Job 
ALTEN GmbH-Firmenlogo
Engineer semiconductor technology (all gender) ALTEN GmbH
München Zum Job 
ALTEN GmbH-Firmenlogo
Embedded Softwareentwickler Automotive (all gender) ALTEN GmbH
München Zum Job 
ALTEN GmbH-Firmenlogo
Requirements Engineer Automotive (all gender) ALTEN GmbH
München Zum Job 
Poppe + Potthoff Präzisionsstahlrohre GmbH-Firmenlogo
Projektingenieur (m/w/d) Produkt- und Prozessoptimierung Poppe + Potthoff Präzisionsstahlrohre GmbH
Werther (Westfalen) Zum Job 
Mynaric-Firmenlogo
Production Manager (m/w/x) Mynaric
Gilching Zum Job 
Swoboda Schorndorf KG-Firmenlogo
Techniker / Ingenieur Qualitätsvorausplanung AQP (m/w/d) Swoboda Schorndorf KG
Schorndorf Zum Job 
Swoboda Schorndorf KG-Firmenlogo
Commodity Manager - Molded Parts (m/w/d) Swoboda Schorndorf KG
Schorndorf Zum Job 
Swoboda Schorndorf KG-Firmenlogo
(Senior) Entwicklungsingenieur (m/w/d) für Sensorik Swoboda Schorndorf KG
Schorndorf 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

    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.