Shor's algorithm

Shor's algorithm (tsz. Shor's algorithms)

1. (informatika) Shor-algoritmus

Shor algoritmusa egy kvantumalgoritmus, amelyet Peter Shor fejlesztett ki 1994-ben. Ez az algoritmus képes polinomiális időben faktorizálni nagy egész számokat – vagyis megtalálni egy szám prímtényezőit sokkal gyorsabban, mint a legjobb ismert klasszikus algoritmusok. Ennek óriási jelentősége van a kriptográfiában, különösen az olyan rendszerek esetében, mint az RSA, amelyek biztonsága a faktorizálás nehézségére épül.

A prímtényezőkre bontás (integer factorization) problémája:

Adott egy nagy egész szám ${\textstyle N}$, találj két nem triviális osztót (azaz ${\textstyle 1<p<N}$), amelyek szorzata ${\textstyle N}$.

Példa: ${\textstyle N=15}$ → megoldás: 3 és 5

A klasszikus algoritmusok ezt nagyon lassan oldják meg nagy számok esetén – exponenciális időben.

Shor algoritmusa viszont kvantumszámítógépen képes ezt polinomiális idő alatt elvégezni!

1. Véletlenszerű választás: Válassz egy véletlen számot ${\textstyle a}$, ahol ${\textstyle 1<a<N}$

2. Legnagyobb közös osztó: Ha ${\textstyle {\text{gcd}}(a,N)>1}$, már meg is van egy osztó!

3. Perióduskeresés (kvantum): Találd meg a ${\textstyle r}$ legkisebb számot, amire:

   $${\displaystyle a^{r}\mod N=1}$$

   Ez a lépés a kvantum része az algoritmusnak, kvantum-Fourier-transzformációval valósul meg.

4. Faktorizálás: Ha ${\textstyle r}$ páros, és ${\textstyle a^{r/2}\not \equiv -1\mod N}$, akkor:

   $${\displaystyle {\text{gcd}}(a^{r/2}\pm 1,N)}$$

   egy nem triviális osztója ${\textstyle N}$-nek.

• Válasszuk ${\textstyle a=2}$

• ${\textstyle {\text{gcd}}(2,15)=1}$

• Keressük ${\textstyle r}$-t, hogy ${\textstyle 2^{r}\equiv 1\mod 15}$

  • ${\textstyle 2^{4}=16\equiv 1\mod 15}$, tehát ${\textstyle r=4}$

• Mivel ${\textstyle r}$ páros, és ${\textstyle 2^{2}=4\not \equiv -1\mod 15}$, akkor:

  $${\displaystyle {\text{gcd}}(4-1,15)={\text{gcd}}(3,15)=3}$$ $${\displaystyle {\text{gcd}}(4+1,15)={\text{gcd}}(5,15)=5}$$

  → Osztók: 3 és 5 ✅

• Klasszikusan: legjobb ismert módszer pl. GNFS → szuperpolinomiális idő

• Shor algoritmusával (kvantum):

  $${\displaystyle O((\log N)^{3})}$$

  Ez exponenciális gyorsulás a klasszikushoz képest.

A RSA titkosítás a faktorizálás nehézségére épül. Ha lenne elérhető kvantumszámítógép, amely képes futtatni Shor algoritmusát nagy számokra, akkor:

• RSA, DSA, Diffie-Hellman → megtörhetők
• Ezért fejlesztik a kvantumbiztos kriptográfiát (pl. lattice-alapú algoritmusokat)

• A perióduskeresés a klasszikus számelmélet egyik központi nehézsége.
• Kvantumszámítógépen ez kvantum-Fourier-transzformációval hatékonyan elvégezhető.
• Ez adja az algoritmus exponenciális gyorsulását.

A Shor algoritmus kis számokra szimulálható IBM Qiskit, Microsoft Q#, vagy más kvantumszimulátor segítségével.

from qiskit.algorithms import Shor
from qiskit.primitives import Sampler
from qiskit.utils import QuantumInstance
from qiskit import Aer

shor = Shor()
result = shor.factor(N=15)
print(result.factors)

Tulajdonság	Érték
Algoritmus neve	Shor’s algorithm
Probléma típusa	Egész szám faktorizálás
Hagyományos idő	Szuperpolinomiális
Kvantumos idő	Polinomiális ${\textstyle O((\log N)^{3})}$
Kritikus hatás	RSA, kriptográfia megtörése
Állapot	Kísérleti / kvantum-szimulátorral működő

• Shor's algorithm - Szótár.net (en-hu)
• Shor's algorithm - Sztaki (en-hu)
• Shor's algorithm - Merriam–Webster
• Shor's algorithm - Cambridge
• Shor's algorithm - WordNet
• Shor's algorithm - Яндекс (en-ru)
• Shor's algorithm - Google (en-hu)
• Shor's algorithm - Wikidata
• Shor's algorithm - Wikipédia (angol)