.svg)
Quanten-Algorithmen: Shor's Algorithmus
Was es ist
Der Shor-Algorithmus ist ein Algorithmus zum Auffinden der Primfaktoren großer Zahlen in Polynomialzeit. Im Bereich der Cybersicherheit ist RSA (Rivest-Shamir-Adleman) eine gängige Verschlüsselungstechnik. RSA basiert auf einem öffentlichen Schlüssel, der das Produkt aus zwei großen Primzahlen ist, die geheim gehalten werden. RSA basiert auf der Annahme, dass ein Computer nicht in der Lage ist, eine sehr große Zahl in ihre Primzahlkomponenten zu zerlegen, da das Zerlegen in Faktoren eine ganz andere Art von Problemlösung ist als die Addition oder Multiplikation. Shors Algorithmus macht sich die quantenmechanischen Eigenschaften der Überlagerung und Interferenz zunutze, um mögliche Lösungen schnell durchzusuchen, obwohl die Methode auch auf einem klassischen Computer in einem viel größeren Zeitrahmen durchgeführt werden könnte.
Laut Thorsten Kleinjung von der Universität Bonn würde es zum Beispiel 1 bis 2 Jahre dauern, N = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396491743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 auf einem PC mit 2,2 GHz Athlon 64 CPU und ≤ 2 GB Speicher zu faktorisieren.
Der Shor-Algorithmus ist ein leistungsfähiges Werkzeug mit dem Potenzial, jede Primzahl zu faktorisieren, was seinem Benutzer die Möglichkeit gibt, viele aktuelle Verschlüsselungen zu knacken. Die heutigen NISQ-Quantencomputer reichen zwar noch nicht aus, um die RSA-Verschlüsselung zu knacken, aber Experten schätzen, dass dies in einigen Jahren möglich sein könnte. In der Tat hat Shors Algorithmus das Interesse an Quantencomputern geweckt.
Zwar sagen einige voraus, dass der Shor-Algorithmus innerhalb von 10 Jahren auf Quantenglühgeräten - nicht-universellen Quantencomputern mit nur spezialisierten Optimierungsanwendungen - ausgeführt werden kann, aber es gibt viele Faktoren, die in diese Berechnung eingehen. Dabei wird davon ausgegangen, dass sich die Anzahl der Annealing-Qubits jedes zweite Jahr verdoppelt, wie es in der Vergangenheit der Fall war. Die Fortschritte beim Annealing von Qubits könnten durch verschiedene Hindernisse behindert werden, die diesen Zeitrahmen verlangsamen, oder die laufende Forschung im Bereich des Annealing oder des universellen Quantencomputers könnte zu Durchbrüchen führen, die bessere Algorithmen oder Technologien zur Beschleunigung dieses Prozesses offenbaren.
Diese Ungewissheit hinsichtlich des Zeitrahmens sowie die Gefahr, dass die RSA-Verschlüsselung unbrauchbar wird, hat die Aufmerksamkeit von benachbarten Bereichen und Regierungen gleichermaßen auf sich gezogen. Eine kürzlich erlassene Verordnung der Vereinigten Staaten, in der ein Zeitplan für die Schaffung von Standards und Rahmenbedingungen für die Post-Quantum-Kryptografie (PQC) und die Entwicklung quantenresistenter Algorithmen festgelegt wurde, zeigt, wie ernst diese Sicherheitslücke sein könnte. Wo es Daten gibt, gibt es auch ein Bedürfnis nach Sicherheit. CIOs/CTOs von Unternehmen auf der ganzen Welt investieren in die Quantenphysik, nachdem sie von den Auswirkungen des Shor-Algorithmus erfahren haben, wobei sie oft ihre Quantenkompetenzen mit anderen Anwendungen verstärken und sich einen Vorteil gegenüber denjenigen verschaffen, die mit ihrer Quantenreise noch warten. Die UnitedHealth Group beispielsweise verfügt über Quantenteams auf drei Kontinenten und hat nach ihrem Einstieg in die Quantenkryptografie begonnen, Anwendungen der künstlichen Intelligenz mit maschinellem Lernen zu untersuchen.
Wie es funktioniert
Das Wesen des Shor-Algorithmus besteht darin, eine schlechte Schätzung eines Faktors in eine viel bessere zu verwandeln, indem man die Periode einer Funktion findet, die den RSA-Schlüssel enthält.
Wir beginnen mit der großen Zahl, die wir faktorisieren wollen, $N$, und einer Anfangsschätzung, $g.$ Es gibt zwei Fälle für diese Anfangsschätzung. Im ersten Fall ist entweder $g$ ein Faktor von $N$ oder er hat einen gemeinsamen Faktor mit $N$. In diesem Fall sind wir dank des Euklidschen Algorithmus oder des schnelleren Euklidischen Algorithmus, einer Methode zum Prüfen oder Finden gemeinsamer Faktoren durch Subtraktion bzw. Modulo, fertig. Um einen Faktor von $N$ zu finden, müssen wir nicht unbedingt einen Faktor erraten, sondern einen, der mit $N$ gemeinsame Faktoren hat, funktioniert auch.
Wenn $g$ weder ein Faktor von $N$ ist noch einen gemeinsamen Faktor hat, dann geht man dazu über, diese Vermutung in eine bessere umzuwandeln. Für zwei beliebige ganze Zahlen, $A$ und $B$, gibt es eine Potenz $p$ und ein Vielfaches $m$, so dass $A^p = m*B +1$. Wir können dies mit einigen Primzahlen, zum Beispiel 3 und 7, demonstrieren.
$3^2 = 9 = 1*7 + 2$
$3^3 = 27 = 3*7 + 6$
$3^4 = 81 = 11*7 + 4$
$3^5 = 243 = 34*7 + 5$
$3^6 = 729 = 104*7 + 1$
Diese Beziehung hilft uns, das Problem anders zu betrachten.
We can write our relationship with our terms: $g^p = m*N +1$. Once we subtract 1 from both sides, getting $g^p-1 = m*N$, we can rewrite this as $(g^{\frac{p}{2}} + 1)(g^{\frac{p}{2}} - 1) = m*N$, as this is a difference of two squares. This looks more like two factors of $N$, for which we are searching, so instead of searching for a better guess $g$, we will now search for a power $p$.
An dieser Stelle kommen die Quantencomputer ins Spiel. Wir können geschickt eine Überlagerung möglicher Kräfte konstruieren, bei der sich alle falschen Schätzungen gegenseitig zerstörerisch beeinflussen.
Um es noch einmal zu wiederholen: Wir suchen nach einer Potenz, auf die wir unsere anfängliche falsche Schätzung erhöhen. Wenn wir den Term der großen Zahl, $m*N$, von diesem potenzierten Term, $g^p$, subtrahieren, brauchen wir einen Rest von 1, oder $g^p - m*N = 1$. Unser System sieht also folgendermaßen aus.
Eingabe der Überlagerung von Potenzen in die Potenzierung:
$$|x\rangle \rightarrow [g^x] \rightarrow |x, g^x\rangle .$$
Geben Sie die Überlagerung der Potenzierungen in die Differenz des großen Zahlterms ein, um den Rest zu finden:
$$|x, g^x\rangle \rightarrow [>m*N] \rightarrow |x, +r\rangle .$$
Und wir wollen, dass dieser Rest gleich 1 ist.
Wir machen uns nun eine strukturelle Beziehung zwischen Potenzierung und modularer Arithmetik zunutze.
$$g^x = m*N + r \rightarrow g^{x+p} = m_1*N + r \rightarrow g^{x+2p} = m_2*N + r$$
Der Rest bleibt unabhängig von linearen Änderungen des Exponenten gleich, d. h. es gibt eine sich wiederholende Eigenschaft mit einer gewissen Periode. Nehmen Sie dieses Beispiel, bei dem verschiedene Potenzen verschiedene Reste erzeugen, die zusammen denselben Rest ergeben.
$$g^{p+10} = g^pg^{10}$$
$$ = (mN + 2)(m_1N + 4)$$
$$ = mm_1N^2+4mN+2m_1N+8$$
$$ = (mm_1\frac{N}{2}+2m+m_1)N + 4\Rightarrow\text{irgendwas} N + 4 $$
$$ = (mm_1\frac{N}{4}+m+\frac{m_1}{2})N + 2\Rightarrow\text{something} N + 2.$$
Wenn wir eine Überlagerung durch unser System eingeben und den Rest messen, erhalten wir eine Überlagerung aller möglichen Potenzen, die nur diesen Rest ergeben. Und diese Restüberlagerung wiederholt sich mit einer Periode der Potenz $p$ oder hat eine Frequenz von $f=\frac{1}{p}$.
So wie eine klassische Fourier-Transformation eine Welle als Funktion der Zeit in eine Funktion der Frequenz übersetzt, so tut dies auch eine Quanten-Fourier-Transformation (QFT), mit einer Überlagerung als Ausgang mit einer Frequenz des Eingangs.
Wenn wir also einen einzelnen Zustand in eine QFT eingeben, ist das Ergebnis eine Überlagerung von Zuständen mit unterschiedlichen Gewichten oder Wahrscheinlichkeiten, die eine Welle mit dem Eingangszustand als Frequenz bilden. Und wenn wir mehrere Zustände in eine QFT eingeben, ist das Ergebnis eine Überlagerung von Überlagerungen - mit destruktiver und konstruktiver Interferenz, die Überlagerungen zu einer Welle kombiniert. Und wenn unsere Eingabe in die QFT eine Superposition mit der Periode $p$ ist, bleibt bei destruktiver Interferenz nur $\frac{1}{p}$ übrig.
Von hier aus berechnen wir einfach unsere bessere Schätzung, $g^{\frac{p}{2}} ± 1$, und iterieren nach Bedarf.
Heutige Quantencomputer sind nur in der Lage, kleine Zahlen wie 15 und 21 zu faktorisieren, während anspruchsvollere Techniken wie Adiabatic Quantum Computing (AQC) 5900 Qubits benötigen, um einige der kleinsten für RSA verwendeten Zahlen zu faktorisieren.
Weitere Informationen über den Algorithmus von Shor finden Sie hier oder hier.
Was es ist
Der Shor-Algorithmus ist ein Algorithmus zum Auffinden der Primfaktoren großer Zahlen in Polynomialzeit. Im Bereich der Cybersicherheit ist RSA (Rivest-Shamir-Adleman) eine gängige Verschlüsselungstechnik. RSA basiert auf einem öffentlichen Schlüssel, der das Produkt aus zwei großen Primzahlen ist, die geheim gehalten werden. RSA basiert auf der Annahme, dass ein Computer nicht in der Lage ist, eine sehr große Zahl in ihre Primzahlkomponenten zu zerlegen, da das Zerlegen in Faktoren eine ganz andere Art von Problemlösung ist als die Addition oder Multiplikation. Shors Algorithmus macht sich die quantenmechanischen Eigenschaften der Überlagerung und Interferenz zunutze, um mögliche Lösungen schnell durchzusuchen, obwohl die Methode auch auf einem klassischen Computer in einem viel größeren Zeitrahmen durchgeführt werden könnte.
Laut Thorsten Kleinjung von der Universität Bonn würde es zum Beispiel 1 bis 2 Jahre dauern, N = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396491743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 auf einem PC mit 2,2 GHz Athlon 64 CPU und ≤ 2 GB Speicher zu faktorisieren.
Der Shor-Algorithmus ist ein leistungsfähiges Werkzeug mit dem Potenzial, jede Primzahl zu faktorisieren, was seinem Benutzer die Möglichkeit gibt, viele aktuelle Verschlüsselungen zu knacken. Die heutigen NISQ-Quantencomputer reichen zwar noch nicht aus, um die RSA-Verschlüsselung zu knacken, aber Experten schätzen, dass dies in einigen Jahren möglich sein könnte. In der Tat hat Shors Algorithmus das Interesse an Quantencomputern geweckt.
Zwar sagen einige voraus, dass der Shor-Algorithmus innerhalb von 10 Jahren auf Quantenglühgeräten - nicht-universellen Quantencomputern mit nur spezialisierten Optimierungsanwendungen - ausgeführt werden kann, aber es gibt viele Faktoren, die in diese Berechnung eingehen. Dabei wird davon ausgegangen, dass sich die Anzahl der Annealing-Qubits jedes zweite Jahr verdoppelt, wie es in der Vergangenheit der Fall war. Die Fortschritte beim Annealing von Qubits könnten durch verschiedene Hindernisse behindert werden, die diesen Zeitrahmen verlangsamen, oder die laufende Forschung im Bereich des Annealing oder des universellen Quantencomputers könnte zu Durchbrüchen führen, die bessere Algorithmen oder Technologien zur Beschleunigung dieses Prozesses offenbaren.
Diese Ungewissheit hinsichtlich des Zeitrahmens sowie die Gefahr, dass die RSA-Verschlüsselung unbrauchbar wird, hat die Aufmerksamkeit von benachbarten Bereichen und Regierungen gleichermaßen auf sich gezogen. Eine kürzlich erlassene Verordnung der Vereinigten Staaten, in der ein Zeitplan für die Schaffung von Standards und Rahmenbedingungen für die Post-Quantum-Kryptografie (PQC) und die Entwicklung quantenresistenter Algorithmen festgelegt wurde, zeigt, wie ernst diese Sicherheitslücke sein könnte. Wo es Daten gibt, gibt es auch ein Bedürfnis nach Sicherheit. CIOs/CTOs von Unternehmen auf der ganzen Welt investieren in die Quantenphysik, nachdem sie von den Auswirkungen des Shor-Algorithmus erfahren haben, wobei sie oft ihre Quantenkompetenzen mit anderen Anwendungen verstärken und sich einen Vorteil gegenüber denjenigen verschaffen, die mit ihrer Quantenreise noch warten. Die UnitedHealth Group beispielsweise verfügt über Quantenteams auf drei Kontinenten und hat nach ihrem Einstieg in die Quantenkryptografie begonnen, Anwendungen der künstlichen Intelligenz mit maschinellem Lernen zu untersuchen.
Wie es funktioniert
Das Wesen des Shor-Algorithmus besteht darin, eine schlechte Schätzung eines Faktors in eine viel bessere zu verwandeln, indem man die Periode einer Funktion findet, die den RSA-Schlüssel enthält.
Wir beginnen mit der großen Zahl, die wir faktorisieren wollen, $N$, und einer Anfangsschätzung, $g.$ Es gibt zwei Fälle für diese Anfangsschätzung. Im ersten Fall ist entweder $g$ ein Faktor von $N$ oder er hat einen gemeinsamen Faktor mit $N$. In diesem Fall sind wir dank des Euklidschen Algorithmus oder des schnelleren Euklidischen Algorithmus, einer Methode zum Prüfen oder Finden gemeinsamer Faktoren durch Subtraktion bzw. Modulo, fertig. Um einen Faktor von $N$ zu finden, müssen wir nicht unbedingt einen Faktor erraten, sondern einen, der mit $N$ gemeinsame Faktoren hat, funktioniert auch.
Wenn $g$ weder ein Faktor von $N$ ist noch einen gemeinsamen Faktor hat, dann geht man dazu über, diese Vermutung in eine bessere umzuwandeln. Für zwei beliebige ganze Zahlen, $A$ und $B$, gibt es eine Potenz $p$ und ein Vielfaches $m$, so dass $A^p = m*B +1$. Wir können dies mit einigen Primzahlen, zum Beispiel 3 und 7, demonstrieren.
$3^2 = 9 = 1*7 + 2$
$3^3 = 27 = 3*7 + 6$
$3^4 = 81 = 11*7 + 4$
$3^5 = 243 = 34*7 + 5$
$3^6 = 729 = 104*7 + 1$
Diese Beziehung hilft uns, das Problem anders zu betrachten.
We can write our relationship with our terms: $g^p = m*N +1$. Once we subtract 1 from both sides, getting $g^p-1 = m*N$, we can rewrite this as $(g^{\frac{p}{2}} + 1)(g^{\frac{p}{2}} - 1) = m*N$, as this is a difference of two squares. This looks more like two factors of $N$, for which we are searching, so instead of searching for a better guess $g$, we will now search for a power $p$.
An dieser Stelle kommen die Quantencomputer ins Spiel. Wir können geschickt eine Überlagerung möglicher Kräfte konstruieren, bei der sich alle falschen Schätzungen gegenseitig zerstörerisch beeinflussen.
Um es noch einmal zu wiederholen: Wir suchen nach einer Potenz, auf die wir unsere anfängliche falsche Schätzung erhöhen. Wenn wir den Term der großen Zahl, $m*N$, von diesem potenzierten Term, $g^p$, subtrahieren, brauchen wir einen Rest von 1, oder $g^p - m*N = 1$. Unser System sieht also folgendermaßen aus.
Eingabe der Überlagerung von Potenzen in die Potenzierung:
$$|x\rangle \rightarrow [g^x] \rightarrow |x, g^x\rangle .$$
Geben Sie die Überlagerung der Potenzierungen in die Differenz des großen Zahlterms ein, um den Rest zu finden:
$$|x, g^x\rangle \rightarrow [>m*N] \rightarrow |x, +r\rangle .$$
Und wir wollen, dass dieser Rest gleich 1 ist.
Wir machen uns nun eine strukturelle Beziehung zwischen Potenzierung und modularer Arithmetik zunutze.
$$g^x = m*N + r \rightarrow g^{x+p} = m_1*N + r \rightarrow g^{x+2p} = m_2*N + r$$
Der Rest bleibt unabhängig von linearen Änderungen des Exponenten gleich, d. h. es gibt eine sich wiederholende Eigenschaft mit einer gewissen Periode. Nehmen Sie dieses Beispiel, bei dem verschiedene Potenzen verschiedene Reste erzeugen, die zusammen denselben Rest ergeben.
$$g^{p+10} = g^pg^{10}$$
$$ = (mN + 2)(m_1N + 4)$$
$$ = mm_1N^2+4mN+2m_1N+8$$
$$ = (mm_1\frac{N}{2}+2m+m_1)N + 4\Rightarrow\text{irgendwas} N + 4 $$
$$ = (mm_1\frac{N}{4}+m+\frac{m_1}{2})N + 2\Rightarrow\text{something} N + 2.$$
Wenn wir eine Überlagerung durch unser System eingeben und den Rest messen, erhalten wir eine Überlagerung aller möglichen Potenzen, die nur diesen Rest ergeben. Und diese Restüberlagerung wiederholt sich mit einer Periode der Potenz $p$ oder hat eine Frequenz von $f=\frac{1}{p}$.
So wie eine klassische Fourier-Transformation eine Welle als Funktion der Zeit in eine Funktion der Frequenz übersetzt, so tut dies auch eine Quanten-Fourier-Transformation (QFT), mit einer Überlagerung als Ausgang mit einer Frequenz des Eingangs.
Wenn wir also einen einzelnen Zustand in eine QFT eingeben, ist das Ergebnis eine Überlagerung von Zuständen mit unterschiedlichen Gewichten oder Wahrscheinlichkeiten, die eine Welle mit dem Eingangszustand als Frequenz bilden. Und wenn wir mehrere Zustände in eine QFT eingeben, ist das Ergebnis eine Überlagerung von Überlagerungen - mit destruktiver und konstruktiver Interferenz, die Überlagerungen zu einer Welle kombiniert. Und wenn unsere Eingabe in die QFT eine Superposition mit der Periode $p$ ist, bleibt bei destruktiver Interferenz nur $\frac{1}{p}$ übrig.
Von hier aus berechnen wir einfach unsere bessere Schätzung, $g^{\frac{p}{2}} ± 1$, und iterieren nach Bedarf.
Heutige Quantencomputer sind nur in der Lage, kleine Zahlen wie 15 und 21 zu faktorisieren, während anspruchsvollere Techniken wie Adiabatic Quantum Computing (AQC) 5900 Qubits benötigen, um einige der kleinsten für RSA verwendeten Zahlen zu faktorisieren.
Weitere Informationen über den Algorithmus von Shor finden Sie hier oder hier.
Über "Der Podcast des Qubit-Typen"
Der Podcast wird von The Qubit Guy (Yuval Boger, unser Chief Marketing Officer) moderiert. In ihm diskutieren Vordenker der Quanteninformatik über geschäftliche und technische Fragen, die das Ökosystem der Quanteninformatik betreffen. Unsere Gäste geben interessante Einblicke in Quantencomputer-Software und -Algorithmen, Quantencomputer-Hardware, Schlüsselanwendungen für Quantencomputer, Marktstudien der Quantenindustrie und vieles mehr.
Wenn Sie einen Gast für den Podcast vorschlagen möchten, kontaktieren Sie uns bitte .
