prime number

Angol

Főnév

prime number (tsz. prime numbers)

(informatika) prímszám

A prímszámok a matematika – különösen a számelmélet – legfontosabb és legrejtélyesebb objektumai közé tartoznak. Egyszerű a definíciójuk, de rendkívül mély és bonyolult tulajdonságokkal rendelkeznek, amelyek évszázadokon át foglalkoztatták a matematikusokat, és a 21. században is központi szerepet játszanak – különösen a kriptográfiában, számításelméletben, és biztonságos kommunikációban.

Mi az a prímszám?

Definíció: Egy egész szám prím, ha nagyobb 1-nél, és csak két pozitív osztója van: 1 és önmaga.

Példák az első néhány prímszámra:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

Az 1 nem prím (és nem összetett), mert csak egy osztója van.
A 2 az egyetlen páros prímszám.
Minden más prímszám páratlan.

Miért fontosak a prímszámok?

1. Az egész számok építőkövei

A számelmélet alaptétele (vagy aritmetikai alaptétel) kimondja:

Minden 1-nél nagyobb egész szám egyértelműen felbontható prímszámok szorzatára (prímtényezős alak).

Ez hasonló ahhoz, ahogy minden vegyület molekulákból áll – az egész számok „molekulái” a prímszámok.

Például:

${\textstyle 30=2\cdot 3\cdot 5}$
${\textstyle 84=2^{2}\cdot 3\cdot 7}$

2. Kriptográfia

A modern nyilvános kulcsú kriptográfia, például az RSA algoritmus, a prímszámok tulajdonságaira épül. Az alapötlet:

Könnyű két nagy prímet összeszorozni.
Nehéz viszont a szorzatból visszakövetkeztetni a tényezőkre (ez a prímtényezőkre bontás problémája).

Ez a nehézség garantálja a titkosítás biztonságát.

Prímszámok eloszlása

1. Végtelen sok prím

Euklidész i.e. 300 körül már bebizonyította, hogy:

Végtelen sok prímszám létezik.

A bizonyítása ma is klasszikus:

Tegyük fel, hogy csak véges sok prím létezik: ${\textstyle p_{1},p_{2},...,p_{n}}$
Vegyük az ${\textstyle N=p_{1}\cdot p_{2}\cdot \cdots \cdot p_{n}+1}$ számot
Ez a szám nem osztható egyik ismert prímmel sem → új prím vagy új oszthatósági viszony

2. Prímszámtétel

A prímszámtétel (Prime Number Theorem, PNT) megadja, hogy a prímek „ritkulnak”, de kiszámítható módon:

A ${\textstyle \pi (n)}$ függvény (nél kisebb prímek száma) közelítőleg ${\textstyle {\frac {n}{\ln n}}}$

Ez azt jelenti, hogy:

10 alatt 4 prím van
100 alatt 25 prím
10⁶ alatt kb. 78,498 prím

A prímszámok sűrűsége csökken, de mindig „előbukkan” újabb.

Prímszámok keresése

A nagy prímszámok keresése gyakran számítástechnikai kihívás és egyben hobbi is. A Mersenne-prímek (olyan prímek, amelyek ${\textstyle 2^{p}-1}$ alakúak) különösen érdekesek, mert gyors algoritmusokkal tesztelhetők.

A világ legnagyobb ismert prímjei gyakran több tízmillió számjegy hosszúak.

Prímtesztek

Prímteszt egy olyan algoritmus, amely eldönti egy számról, hogy prím-e. Típusai:

Determinista (pl. AKS-prímteszt – 2002 óta létezik polinomidőben)
Valószínűségi (pl. Miller–Rabin, Fermat-teszt) – gyorsabb, de kis hibával dolgozik

Prímszámok típusai

A prímszámok különféle tulajdonságaik szerint osztályozhatók:

Ikerszámok: Olyan prímek, amelyek páronként csak 2-vel különböznek (pl. 11 és 13)
Mersenne-prímek: ${\textstyle 2^{p}-1}$ , ha p is prím
Sophie Germain-prímek: Olyan prímek, ahol ${\textstyle 2p+1}$ is prím
Fermat-prímek: ${\textstyle 2^{2^{n}}+1}$ alakú számok
Palindrom prímek: Olyan prímek, amelyek számjegyei visszafelé olvasva is ugyanazt adják (pl. 131, 797)

Nyitott problémák a prímszámelméletben

1. Ikerszám sejtés

Végtelen sok ikerprím létezik?

Ezt eddig senki sem tudta bizonyítani vagy cáfolni. Ez az egyik legrégebbi nyitott sejtés a számelméletben.

2. Riemann-sejtés

A prímszámok eloszlásának egyik legfontosabb (és legrejtélyesebb) összefüggése a Riemann-zéta-függvény zérusaihoz kapcsolódik.

A Riemann-sejtés kimondja, hogy a nem triviális zérusok mindnek valós része ${\textstyle {\frac {1}{2}}}$ .

Ennek igazsága mély hatással van a prímszámok eloszlásának pontosságára.

Prímszámok a gyakorlatban

1. Titkosítás

Az RSA algoritmus két nagy prím szorzatán alapul.
Az elliptikus görbéken alapuló titkosítás is gyakran használ prímszámokat a végeselemek meghatározásához.

2. Hashing, hibajavítás, véletlenszámok

Prímszámokat használnak kódoláselméletben, véletlenszám-generálásban, adatbázis-keresésekben, és kriptográfiai kivonatolásban (hashing).

Összegzés

A prímszámok:

Egyszerűen definiálhatóak, de matematikailag rendkívül komplexek.
Alapvető szerepet játszanak az egész számok szerkezetében.
Központi jelentőségűek a kriptográfiában és a biztonságtechnikában.
Eloszlásuk továbbra is részben titokzatos, és számos híres sejtés (pl. Riemann, ikerszám) kapcsolódik hozzájuk.
Hatékony algoritmusok (pl. Miller–Rabin, AKS) segítségével számítógéppel is vizsgálhatók, de a matematikai struktúrájuk még mindig aktív kutatás tárgya.

A prímszámok olyan egyszerűséggel rejtik magukban a mélységet, mint kevés más matematikai objektum. Ezért mondta Paul Erdős is:

“A prímszámok Isten titkai, és mi csak próbáljuk megfejteni őket.”

További információk

prime number - Szótár.net (en-hu)
prime number - Sztaki (en-hu)
prime number - Merriam–Webster
prime number - Cambridge
prime number - WordNet
prime number - Яндекс (en-ru)
prime number - Google (en-hu)
prime number - Wikidata
prime number - Wikipédia (angol)