Fermat-algoritmus
Kiejtés
- IPA: [ ˈfɛrmɒtɒlɡoritmuʃ]
Főnév
- (matematika) ### **Fermat-algoritmus**
A **Fermat-algoritmus** egy hatékony módszer az **összetett számok faktorizálására**. Az algoritmus Pierre de Fermat nevéhez fűződik, és azon az elven alapul, hogy egy egész szám felírható két négyzetszám különbségeként:
\[ N = a^2 - b^2 \]
Ez az azonosság pedig így alakítható át: \[ N = (a - b)(a + b) \]
Ha sikerül megfelelő \(a\) és \(b\) értékeket találni, akkor \(N\) két tényezőre bontható: \((a - b)\) és \((a + b)\).
---
- **Fő ötlet**
1. \(N\) egész számot keresünk, amely két négyzetszám különbségeként írható fel (\(N = a^2 - b^2\)). 2. Ezután:
- \(a = \lceil \sqrt{N} \rceil\), azaz \(a\) az \(N\) négyzetgyökének felfelé kerekített értéke.
- \(b^2 = a^2 - N\), ahol \(b^2\) is négyzetszám.
3. Ha \(b^2\) négyzetszám, akkor \(b = \sqrt{b^2}\), és a faktorizáció:
\[ N = (a - b)(a + b) \]
---
- **Algoritmus lépései**
1. **Inicializálás**:
- Számítsd ki \(a = \lceil \sqrt{N} \rceil\).
- Kezdd \(b^2 = a^2 - N\)-vel.
2. **Iteráció**:
- Ellenőrizd, hogy \(b^2\) négyzetszám-e.
- Ha igen, számítsd ki \(b = \sqrt{b^2}\), és állítsd elő a faktorizációt.
- Ha nem, növeld \(a\)-t (\(a = a + 1\)), és ismételd meg az ellenőrzést.
3. **Befejezés**:
- Addig folytasd, amíg \(b^2\) négyzetszám lesz, vagy kiderül, hogy \(N\) prím.
---
- **Időbonyolultság**
- Az algoritmus hatékonysága attól függ, hogy az első megfelelő \(a\) és \(b\) értékek milyen gyorsan találhatók meg. - Átlagos esetben \(O(N^{1/4})\), mivel a négyzetgyök környékén kell próbálkozni.
---
- **Pszeudokód**
``` FermatFactorization(N):
a = ceil(sqrt(N))
while True:
b2 = a^2 - N
if b2 is a perfect square:
b = sqrt(b2)
return (a - b, a + b)
a = a + 1
```
---
- **Python implementáció**
```python import math
def fermat_factorization(n):
if n <= 0:
return None # Csak pozitív egész számokra alkalmazható
if n % 2 == 0:
return (2, n // 2) # Páros szám faktorizálása
a = math.ceil(math.sqrt(n))
b2 = a * a - n
while not is_perfect_square(b2):
a += 1
b2 = a * a - n
b = int(math.sqrt(b2))
return (a - b, a + b)
def is_perfect_square(x):
s = int(math.sqrt(x)) return s * s == x
- Példa használat
n = 5959 factors = fermat_factorization(n) print(f"A(z) {n} faktorizációja: {factors}") ```
- Kimenet**:
``` A(z) 5959 faktorizációja: (59, 101) ```
---
- **C++ implementáció**
```cpp
- include <iostream>
- include <cmath>
using namespace std;
bool is_perfect_square(long long x) {
long long s = sqrt(x); return s * s == x;
}
pair<long long, long long> fermat_factorization(long long n) {
if (n <= 0) {
return {-1, -1}; // Csak pozitív számokra
}
if (n % 2 == 0) {
return {2, n / 2}; // Páros szám faktorizálása
}
long long a = ceil(sqrt(n));
long long b2 = a * a - n;
while (!is_perfect_square(b2)) {
a += 1;
b2 = a * a - n;
}
long long b = sqrt(b2);
return {a - b, a + b};
}
int main() {
long long n = 5959;
auto factors = fermat_factorization(n);
cout << "A(z) " << n << " faktorizációja: (" << factors.first << ", " << factors.second << ")" << endl;
return 0;
} ```
- Kimenet**:
``` A(z) 5959 faktorizációja: (59, 101) ```
---
- **Előnyök**
1. **Egyszerűség**:
- Az algoritmus koncepciója könnyen érthető és implementálható.
2. **Hatékony négyzetszámok közelében**:
- Az algoritmus különösen jól működik, ha a szám két tényezője hasonló nagyságrendű.
3. **Determinált**:
- Mindig pontos eredményt ad, ha megfelelő tényezőket talál.
---
- **Hátrányok**
1. **Nagy különbségű tényezők**:
- Ha a szám tényezői nagyon eltérőek, az algoritmus lassú lehet.
2. **Speciális esetek**:
- Nem alkalmazható hatékonyan például prímszámokra, mert azok nem faktorizálhatók.
3. **Iterációs költség**:
- Az algoritmus addig iterál, amíg megfelelő \(b^2\)-t talál, ami időigényes lehet nagy számok esetén.
---
- **Összegzés**
A **Fermat-algoritmus** hatékony eszköz az egész számok faktorizálására, különösen akkor, ha a szám két tényezője közel áll egymáshoz. Az egyszerűsége miatt gyakran használják kisebb számok esetén vagy oktatási célokra, de nagyobb számoknál és eltérő tényezők esetén modern algoritmusok, mint például a **Rho-pollard faktorizálás** vagy a **kvadratikus szita** hatékonyabbak lehetnek.
- Fermat-algoritmus - Értelmező szótár (MEK)
- Fermat-algoritmus - Etimológiai szótár (UMIL)
- Fermat-algoritmus - Szótár.net (hu-hu)
- Fermat-algoritmus - DeepL (hu-de)
- Fermat-algoritmus - Яндекс (hu-ru)
- Fermat-algoritmus - Google (hu-en)
- Fermat-algoritmus - Helyesírási szótár (MTA)
- Fermat-algoritmus - Wikidata
- Fermat-algoritmus - Wikipédia (magyar)