Shor-algoritmus
Kiejtés
- IPA: [ ˈʃhorɒlɡoritmuʃ]
Főnév
Shor-algoritmus
A Shor-algoritmus egy kvantumalgoritmus, amelyet Peter Shor fejlesztett ki 1994-ben. Ez egy hatékony módszer az egész számok faktorizálására, amely egy klasszikus számítógépen szinte lehetetlenül sokáig tartó feladatot polinomiális időben képes megoldani kvantumszámítógépen.
Fő ötlet
A Shor-algoritmus az egész számok faktorizálását (pl. (N = 15), amely (3 )) egy számelméleti probléma megoldására, az ismétlődési periódus keresésére redukálja. Az algoritmus kvantumszámítógépen a Fourier-transzformáció segítségével gyorsan megtalálja ezt a periódust, amelyből a szám faktorizálható.
Probléma megfogalmazása
Adott egy egész szám (N), amelyet (N = p q) alakban szeretnénk felbontani, ahol (p) és (q) prímszámok.
Klasszikus megközelítés:
- Egy klasszikus algoritmus esetén a faktorizáció (O(e^{c })) időigényű.
Shor-algoritmus futási ideje:
- Polinomiális idő, (O((N)^2 (N) (N))), amely drámai gyorsulás.
Működés
1. Véletlenszerű alap kiválasztása
Válassz egy véletlenszerű (a) számot ((1 < a < N)).
2. Tesztelés az oszthatóságra
Ha ((a, N) > 1), akkor ez egy osztó, és kész a faktorizáció.
3. Periódus ((r)) keresése
Határozzuk meg az (f(x) = a^x N) függvény ismétlődési periódusát ((r)): [ f(x) = f(x + r), x ] Ez kvantum-számítással gyorsan megoldható.
4. Faktorizáció periódus alapján
Ha (r) páros, és (a^{r/2} N), akkor: [ p = (a^{r/2} - 1, N), q = (a^{r/2} + 1, N) ]
Ha ez nem ad megoldást, kezdjük újra egy másik (a) értékkel.
Algoritmus lépései
- Klasszikus előfeldolgozás:
- Válassz (a)-t véletlenszerűen.
- Ellenőrizd az oszthatóságot (((a, N))).
- Kvantumrész: Perióduskeresés:
- Hozz létre egy szuperpozíciót: [ _{x=0}^{Q-1} |x|f(x) ]
- Végezze el a kvantumos Fourier-transzformációt ((QFT)) az első regiszteren: [ QFT: |x _{y=0}^{Q-1} e^{2i xy / Q} |y ]
- Mérd meg az első regisztert, amelyből a periódus ((r)) visszafejthető.
- Klasszikus utófeldolgozás:
- Ha (r) érvényes (páros, és (a^{r/2} N)), számítsd ki (p)-t és (q)-t.
Pszeudokód
Shor(N): 1. Válassz véletlenszerű számot: 1 < a < N 2. Számítsd ki: gcd(a, N) - Ha gcd(a, N) > 1, térj vissza osztóval. 3. Kvantumos perióduskeresés: - Keresd meg \(r\)-t, hogy \(a^r \mod N = 1\). 4. Ha \(r\) páros és \(a^{r/2} \not\equiv -1 \mod N\): - Számítsd ki: p = gcd(a^{r/2} - 1, N) q = gcd(a^{r/2} + 1, N) - Térj vissza \(p\)-vel és \(q\)-val. 5. Ha nem sikerült, ismételd meg másik \(a\)-val.
Python implementáció (szimuláció)
Az alábbi kód a Shor-algoritmus klasszikus szimulációját mutatja be.
import math
import random
from sympy import gcd
def shor(N):
if N % 2 == 0:
return 2
while True:
a = random.randint(2, N - 1)
g = gcd(a, N)
if g > 1:
return g
# Kvantumos perióduskeresés szimulálva
r = find_period(a, N)
if r is None or r % 2 != 0:
continue
# Faktorizáció
x = pow(a, r // 2, N)
if x == N - 1:
continue
p = gcd(x - 1, N)
q = gcd(x + 1, N)
if p * q == N:
return p, q
def find_period(a, N):
"""Klasszikus perióduskeresés szimulálása."""
r = 1
while pow(a, r, N) != 1:
r += 1
if r > N:
return None
return r
# Példa
N = 15
result = shor(N)
print(f"A(z) {N} faktorizációja: {result}")
Kimenet:
A(z) 15 faktorizációja: (3, 5)
Qiskit implementáció
A Qiskit könyvtárat használva a kvantumos perióduskeresést is megvalósíthatjuk.
from qiskit import Aer, QuantumCircuit, execute
def quantum_fourier_transform(circuit, n):
for i in range(n):
for j in range(i):
circuit.cp(math.pi / (2 ** (i - j)), j, i)
circuit.h(i)
def shor_circuit(N, a):
n = math.ceil(math.log(N, 2)) * 2
circuit = QuantumCircuit(n, n)
# Inicializáció
circuit.h(range(n))
circuit.barrier()
# Oracle
for i in range(n):
circuit.cx(i, (i + a) % n)
# Kvantumos Fourier-transzformáció
quantum_fourier_transform(circuit, n)
circuit.barrier()
# Mérési eredmények
circuit.measure(range(n), range(n))
return circuit
# Példa (N = 15, a = 7)
qc = shor_circuit(15, 7)
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
counts = result.get_counts()
print("Mérési eredmények:", counts)
Előnyök
- Exponenciális gyorsítás:
- Klasszikus algoritmusokhoz képest exponenciális gyorsulást biztosít.
- Kriptográfiai alkalmazások:
- Hatékonyan támadja a RSA titkosítást.
Hátrányok
- Kvantumszámítógép szükségessége:
- Nagy teljesítményű kvantumszámítógép nélkül nem használható.
- Zajos kvantumhardver:
- Jelenlegi kvantumszámítógépek nem elég stabilak a nagy számok faktorizálására.
Összegzés
A Shor-algoritmus a kvantumszámítástechnika egyik legfontosabb eredménye, amely forradalmasította a kriptográfia és a számelmélet világát. Bár jelenleg a gyakorlati alkalmazások korlátozottak, a jövőbeni fejlesztések lehetővé tehetik nagy számok hatékony faktorizálását, komoly kihívást jelentve a mai titkosítási rendszerek számára.
- Shor-algoritmus - Értelmező szótár (MEK)
- Shor-algoritmus - Etimológiai szótár (UMIL)
- Shor-algoritmus - Szótár.net (hu-hu)
- Shor-algoritmus - DeepL (hu-de)
- Shor-algoritmus - Яндекс (hu-ru)
- Shor-algoritmus - Google (hu-en)
- Shor-algoritmus - Helyesírási szótár (MTA)
- Shor-algoritmus - Wikidata
- Shor-algoritmus - Wikipédia (magyar)