Legendre-Kraitchik-algoritmus
Kiejtés
- IPA: [ ˈlɛɡɛndrɛkrɒjithikɒlɡoritmuʃ]
Főnév
- (matematika) ### **Legendre-Kraitchik-algoritmus**
A **Legendre-Kraitchik-algoritmus** egy faktorizálási módszer, amely két szám közötti **négyzetszámok közötti különbségen** alapul, azaz az azonosságon:
\[ N = a^2 - b^2 = (a - b)(a + b) \]
Ez az algoritmus Pierre de Fermat négyzetszám-különbségen alapuló módszerének általánosítása, amelyet **Maurice Kraitchik** fejlesztett tovább az 1920-as években. A módszer előkészíti a modern **kvadratikus szita** algoritmus alapjait, amelyet széles körben használnak ma is nagy számok faktorizálására.
---
- **Fő ötlet**
1. **Négyzetszámok vizsgálata**:
- Keressünk olyan \(x\) és \(y\) számokat, amelyek kielégítik az alábbi egyenletet:
\[
x^2 \equiv y^2 \pmod{N}
\]
Azaz:
\[
(x - y)(x + y) \equiv 0 \pmod{N}
\]
2. **Faktorokra bontás**:
- Az \(x^2 - y^2\) alakra hozott maradékot faktorizálva két tényezőt kapunk, amelyek közül az egyik lehet \(N\) egy nem triviális osztója.
3. **Lineáris algebra alkalmazása**:
- Keresünk olyan \(x_i\)-k halmazát, ahol a megfelelő \((x_i^2 \mod N)\) szorzata teljes négyzet. - Ezután a megfelelő \(x\) és \(y\) értékeket használjuk a faktorizáláshoz.
---
- **Algoritmus lépései**
- **1. Alapbeállítások**
- Válasszuk ki az \(N\)-hez közeli négyzetszámokat \(x^2\)-ként (\(x\) növekvő természetes számok). - Számítsuk ki a maradékot \(x^2 \mod N\).
- **2. Prímfaktor-alap kiválasztása**
- Válasszunk egy prímekből álló halmazt (\(P\)), amelyek osztói lesznek a faktorizálandó \(N\)-hez kapcsolódó maradékoknak.
- **3. Szorzatok keresése**
- Gyűjtsük össze azokat a \(x^2 \mod N\) maradékokat, amelyek csak a prímfaktor-alap prímjeire bonthatók.
- **4. Lineáris kongruencia megoldása**
- Keressünk egy olyan kombinációt a gyűjtött számok között, amelyek szorzata teljes négyzetet ad. - Ezt mátrixalgebra segítségével hatékonyan megoldhatjuk.
- **5. Faktorokra bontás**
- Ha \(x^2 \equiv y^2 \pmod{N}\), akkor \((x - y)\) és \((x + y)\) osztói lesznek \(N\)-nek.
---
- **Időbonyolultság**
- Az algoritmus komplexitása \(O(\sqrt{N})\), de a prímfaktor-alap és a lineáris algebrai megoldások bonyolultsága miatt lassú lehet nagy számok esetén.
---
- **Pszeudokód**
``` LegendreKraitchik(N):
1. Válassz prímfaktor-alapot P.
2. Keresd meg az x^2 mod N értékeket az x növekvő értékeire.
3. Gyűjtsd össze azokat az x-eket, ahol x^2 mod N csak a P prímek szorzataként írható fel.
4. Lineáris algebra segítségével találd meg azt az x csoportot, amelynek szorzata teljes négyzet.
5. Számítsd ki a következőket:
y = sqrt(prod(x^2 mod N))
gcd(x - y, N) és gcd(x + y, N) osztói N-nek.
6. Térj vissza a nem triviális faktorokkal.
```
---
- **Python implementáció**
```python import math from sympy import gcd from itertools import combinations
def is_square(n):
"""Ellenőrzi, hogy n teljes négyzet-e.""" root = int(math.sqrt(n)) return root * root == n
def factorize_legendre_kraitchik(N):
"""Faktorokra bontás a Legendre-Kraitchik-algoritmus segítségével.""" x = math.ceil(math.sqrt(N)) found = []
# Gyűjtjük az x^2 mod N értékeket
while len(found) < 10: # Legyen legalább 10 elem
y2 = (x * x) % N
if is_square(y2):
found.append((x, int(math.sqrt(y2))))
x += 1
# Kombinációk keresése
for subset in combinations(found, 2):
x1, y1 = subset[0]
x2, y2 = subset[1]
# Ellenőrizzük, hogy gcd nem triviális
factor1 = gcd(x1 - y1, N)
factor2 = gcd(x1 + y1, N)
if factor1 > 1 and factor1 < N:
return factor1, N // factor1
return None
- Példa
N = 5959 factors = factorize_legendre_kraitchik(N) print(f"A(z) {N} faktorizációja: {factors}") ```
- Kimenet**:
``` A(z) 5959 faktorizációja: (59, 101) ```
---
- **Előnyök**
1. **Tudományos alap**:
- Tisztán elméleti alapon működik, és nincs szüksége probabilisztikus megközelítésre.
2. **Praktikus kisebb számokhoz**:
- Hatékonyabb, mint a naiv próbálkozások, ha \(N\) két közeli tényező szorzata.
3. **Alapja a modern algoritmusoknak**:
- A kvadratikus szita és az általános szita algoritmusok erre épülnek.
---
- **Hátrányok**
1. **Nagy számok esetén lassú**:
- Nagy számok faktorizálása esetén más módszerek, például a kvadratikus szita hatékonyabb.
2. **Lineáris algebra szükségessége**:
- A faktorizálás mátrixalgebrai lépései nagy memóriaigényűek lehetnek.
---
- **Alkalmazások**
1. **Számelmélet**:
- Számok faktorizálása és prímtényezők meghatározása.
2. **Kriptográfia**:
- RSA-kulcsok faktorizálásának megértése és támadása.
---
- **Összegzés**
A **Legendre-Kraitchik-algoritmus** egy hatékony elméleti eszköz, amely a modern faktorizálási algoritmusok alapját képezi. Bár a gyakorlati használata korlátozott, kisebb számok és közeli tényezők esetén jól működik. Az algoritmus történelmi jelentősége miatt fontos mérföldkő a faktorizálási módszerek fejlődésében.
- Legendre-Kraitchik-algoritmus - Értelmező szótár (MEK)
- Legendre-Kraitchik-algoritmus - Etimológiai szótár (UMIL)
- Legendre-Kraitchik-algoritmus - Szótár.net (hu-hu)
- Legendre-Kraitchik-algoritmus - DeepL (hu-de)
- Legendre-Kraitchik-algoritmus - Яндекс (hu-ru)
- Legendre-Kraitchik-algoritmus - Google (hu-en)
- Legendre-Kraitchik-algoritmus - Helyesírási szótár (MTA)
- Legendre-Kraitchik-algoritmus - Wikidata
- Legendre-Kraitchik-algoritmus - Wikipédia (magyar)