computational number theory (tsz. computational number theories)
Ez a terület kritikus fontosságú többek között a kriptográfia, a prímszámokkal kapcsolatos eljárások, a matematikai számítások optimalizálása és az osztályozási problémák szempontjából is.
| Fogalom | Jelentés |
|---|---|
| Moduláris aritmetika | Számolás modulo n, pl. 7 mod 3 = 1
|
| Prímteszt | Döntés, hogy egy szám prím-e |
| Nagy számok faktorizálása | Nagy egész szám prímtényezőkre bontása |
| Legnagyobb közös osztó (GCD) | gcd(a, b) – legnagyobb d, ami osztja a-t és b-t
|
| Multiplikatív inverz | Olyan x, hogy a * x ≡ 1 (mod n)
|
| Euler-függvény (φ(n)) | n-nél kisebb és n-nel relatív prím számok száma
|
| Algoritmus | Leírás |
|---|---|
| Euclid-algoritmus | GCD kiszámítás lineáris időben |
| Moduláris hatványozás | Pl. (a^b mod n) hatékony kiszámítása
|
| Miller-Rabin teszt | Gyors, valószínűségi prímteszt |
| AKS teszt | Determinisztikus, polinomiális idejű prímteszt |
| Pollard’s Rho | Faktorizálási algoritmus kis közös osztók keresésére |
| Elliptikus görbe-alapú módszerek | Prímteszt és faktorizálás elliptikus görbékkel |
A számítási számelmélet a modern titkosítás alapja:
| Kriptográfiai rendszer | Számelméleti probléma |
|---|---|
| RSA | Nagy számok faktorizálása |
| Diffie-Hellman | Diszkrét logaritmus probléma |
| ECC (Elliptic Curve Crypto) | Diszkrét logaritmus elliptikus görbéken |
| Lattice-alapú kripto | Számelmélet rácsszerkezetekkel |
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(1071, 462)) # ➜ 21
def modinv(a, m):
a0, m0, x0, x1 = a, m, 0, 1
while m:
q = a // m
a, m = m, a % m
x0, x1 = x1 - q * x0, x0
return x1 % a0
print(modinv(3, 11)) # ➜ 4, mert 3*4 ≡ 1 mod 11
| Eszköz | Funkció |
|---|---|
| SageMath | Nyílt forrású matematikai rendszer |
| PARI/GP | Gyors számelméleti számítások |
| GMP | Arbitrary precision aritmetika |
| Mathematica / Maple | Szimbolikus és számelméleti számítások |
| Python + sympy | Számelmélet és algebrai számítások szkriptkörnyezetben |
A computational number theory célja, hogy hatékony algoritmusokat és számítógépes módszereket fejlesszen számelméleti problémák megoldására, különösen a prímek, kongruenciák, faktorizáció és moduláris műveletek terén. Alkalmazása kulcsfontosságú a kriptográfiában, biztonságos kommunikációban, és a tudományos számításokban.