prímteszt
Kiejtés
- IPA: [ ˈpriːmtɛst]
Főnév
prímteszt
- (matematika, algoritmusok, számelmélet) Prímteszten a matematikában vagy informatikában olyan (determinisztikus) algoritmust vagy indeterminisztikus (például valószínűség-elméleti) módszereket is megengedő eljárást értünk, melynek ismeretében bármely adott egész számról, vagy csak bizonyos típusú számokról (véges sok lépésben) el tudjuk dönteni, hogy prímszám-e, vagy pedig összetett. Ettől lényegesen különböző és sokkal nehezebb feladat egy adott szám prímtényezőinek a megtalálása (prímfelbontás).
Prímteszt
A prímteszt algoritmusok célja annak eldöntése, hogy egy adott szám prímszám-e. Egy szám prím, ha nagyobb, mint (1), és csak (1) és önmaga osztói vannak. A prímtesztek számos típusúak lehetnek, a legegyszerűbb iteratív osztásos módszertől kezdve a bonyolultabb probabilisztikus és determinisztikus algoritmusokig.
Algoritmusok
1. Egyszerű iteratív osztásos prímteszt
A legegyszerűbb módszer, amely egy szám oszthatóságát vizsgálja.
Lépések: 1. Ha a szám kisebb, mint 2, akkor nem prím. 2. Ellenőrizd, hogy osztható-e (2)-vel. 3. Ellenőrizd a (3)-tól ()-ig tartó számokkal való oszthatóságot.
Időbonyolultság: (O())
Python implementáció:
def is_prime_simple(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# Példa
print(is_prime_simple(29)) # True
print(is_prime_simple(30)) # False
2. Eratoszthenész szitája
Egy hatékony algoritmus az összes prím meghatározására (1) és egy adott (n) között.
Lépések: 1. Hozz létre egy logikai listát az (1)-től (n)-ig terjedő számokról. 2. Jelöld ki a (2)-t mint prím. 3. Szorzataik kizárásával (nem prímszámként megjelölésével) iteratívan haladj.
Időbonyolultság: (O(n n))
Python implementáció:
def sieve_of_eratosthenes(limit):
primes = [True] * (limit + 1)
primes[0] = primes[1] = False
for i in range(2, int(limit ** 0.5) + 1):
if primes[i]:
for j in range(i * i, limit + 1, i):
primes[j] = False
return [i for i, is_prime in enumerate(primes) if is_prime]
# Példa
print(sieve_of_eratosthenes(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
3. Miller-Rabin prímteszt
Egy probabilisztikus prímteszt, amely megvizsgálja, hogy egy szám valószínűleg prím-e. Nagy számok esetén hatékony.
Lépések: 1. Írd fel (n-1 = 2^r d) alakban ((d) páratlan). 2. Véletlenszerűen válassz egy (a)-t ((2 a n-2)). 3. Ellenőrizd, hogy (a^d n = 1), vagy ((a{2j d} n = n-1)) valamelyik (0 j < r)-re. 4. Ismételd meg a tesztet néhány különböző (a)-val.
Időbonyolultság: (O(k ^3 n)), ahol (k) az ismétlések száma.
Python implementáció:
import random
def miller_rabin(n, k=5): # k az ismétlések száma
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
# Írjuk fel n-1 = 2^r * d alakban
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n) # a^d % n
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
# Példa
print(miller_rabin(29)) # True
print(miller_rabin(30)) # False
4. AKS prímteszt
Egy determinisztikus algoritmus, amely bizonyítja, hogy egy szám prím-e. Az AKS prímteszt polinomiális időben fut, de implementációja és futási ideje miatt ritkán használják.
Időbonyolultság: (O(^6 n))
Összehasonlítás
| Algoritmus | Időbonyolultság | Előnyök | Hátrányok |
|---|---|---|---|
| Iteratív osztásos teszt | (O()) | Egyszerű, könnyen érthető | Lassú nagy számoknál |
| Eratoszthenész szitája | (O(n n)) | Hatékony prímek generálására | Sok memóriát igényel nagy (n)-re |
| Miller-Rabin teszt | (O(k ^3 n)) | Gyors, nagy számokra alkalmas | Probabilisztikus |
| AKS prímteszt | (O(^6 n)) | Determinisztikus | Nehéz implementáció, lassú |
Példák
Iteratív teszt:
print(is_prime_simple(97)) # True
Eratoszthenész szitája:
print(sieve_of_eratosthenes(100)) # [2, 3, 5, 7, 11, 13, ..., 97]
Miller-Rabin teszt:
print(miller_rabin(561)) # False, mert 561 kompozit (Carmichael-szám)
Összegzés
A választott prímteszt algoritmus a probléma méretétől és jellegétől függ: - Kisebb számok: Iteratív osztásos teszt vagy Eratoszthenész szitája. - Nagy számok: Miller-Rabin teszt. - Bizonyított prímekhez: Determinisztikus algoritmusok, például AKS.
Ezek az algoritmusok fontosak kriptográfiában, számelméletben és adatelemzésben.