A Shor-algoritmus egy kvantumalgoritmus, amelynek a lényege egy adott N szám periódusának megkeresése. Klasszikus számítógéppel (kvantumos lépések nélkül) a periódus megkeresése nem hatékony, de a megadott periódusból a faktorizálás már könnyen elvégezhető. Az alábbi Python-kód a Shor-algoritmus klasszikus lépéseit (moduláris hatványozás és legnagyobb közös osztó) mutatja be:
---------------------------
import math
import random
def gcd(a, b):
"""Legnagyobb közös osztó (LNKO) euklideszi algoritmussal."""
while b != 0:
a, b = b, a % b
return a
def find_period(N, a):
"""
Megkeresi az 'a' szám periódusát modulo N.
Klasszikus számítógépen ez exponenciális ideig tart,
de a Shor-algoritmus kvantum része ezt polinomiális időre csökkenti.
"""
if gcd(a, N) > 1:
raise ValueError("Az 'a' és 'N' nem relatív prímek. Véletlenül találtál egy osztót!")
r = 1
# Moduláris hatványozás: (a^r) mod N
while (a**r) % N != 1:
r += 1
return r
def shor_factors(N):
"""Klasszikus faktorizációs segédfüggvény a Shor-algoritmus logikájával."""
if N % 2 == 0:
return 2, N // 2
# Véletlenszerű 'a' választása 1 < a < N
a = random.randint(2, N - 1)
# 1. lépés: LNKO kiszámítása
g = gcd(a, N)
if g > 1:
return g, N // g
# 2. lépés: Periódus (r) keresése
try:
r = find_period(N, a)
except ValueError as e:
return str(e)
# 3. lépés: Ha a periódus páratlan, próbálkozz újra
if r % 2 != 0:
return "Páratlan periódus adódott, indítsd újra az algoritmust!"
# 4. lépés: Faktorok kiszámítása
half_pow = a**(r // 2)
factor1 = gcd(half_pow - 1, N)
factor2 = gcd(half_pow + 1, N)
return factor1, factor2
# Példa futtatás
N = 23131315
eredmeny = shor_factors(N)
print(f"A {N} faktorai a következők: {eredmeny}")
------------
A 2313131515 faktorai a következők: (5, 462626303)
** Process exited - Return Code: 0 **
Nincsenek megjegyzések:
Megjegyzés küldése