Úristen. Remélem soha nem jártál felsõoktatási intézménynek még a közelében sem, mert annyi hülyeséget hordtál össze, hogy szégyent hoznál vele a teljes magyar matematikaoktatásra.
Kezdjük ott, hogy amit leírtál, az az ún. Erathosztenészi szita-módszer elsõ két lépése (ami egyébként egy roppant naiv és lassú módja a prímtesztelésnek), és nem, nem "nyüzsögnek" a hattal osztható számok mellett a prímek. Egészen konkrétan az N-nél kisebb prímek száma nagyjából N/ln(N) a prímszámtétel alapján.
A nyilvános kulcsú titkosítás (amelyre "kétkulcsos kódolás"-ként hivatkoztál...) pedig nem azért mûködik, mert nem ismerjük az összes prímet tetszõlegesen nagy N-ig, hanem azért, mert nincs hatékony (a bemeneti szám hosszának polinomjával korlátos lépésszámot igénylõ) algoritmusunk tetszõleges egészek prímfelbontásának meghatározására. De ez utóbbi is csak az RSA-kódolásra igaz - más asszimetrikus kriptográfiai sémák merõben eltérõ módszereket használnak, pl. elliptikus görbéket, a diszkrét logaritmus problémáját stb.
Egyébként egy szám prím voltának ellenõrzése a 2002-ben publikált AKS prímteszt óta az algoritmikus értelemben könnyû problémák közé tartozik - a Mersenne-prímek keresése nem azért tart sokáig mert nem értjük a prímeket, hanem azért, mert csillagászatian nagy számokról van szó. Ugye ha végiggondoljuk, akkor az új csúcstartó (2^57885161-1) bináris reprezentációja 57 885 161 darab 1-esbõl áll, azaz nagyjából 7 MByte-ot igényelne a szám puszta tárolása is (persze nyilván nem naiv osztási próbával végzik a Mersenne-prímek tesztelését, hiszen a Lucas-Lehmer prímteszt kifejezetten a Mersenne-prímek struktúrájára lett kitalálva).
Néhány további érdekesség a prímekkel kapcsolatban:
- a mai napig bizonyításra/cáfolatra váró ikerprím sejtész szerint végtelen sok (P, P+2)-alakú prím-pár létezik, ilyenek a (3,5), (5,7), (11,13), (17, 19) stb.
- noha nem tudjuk mennyien vannak, Brun bebizonyította az ikerprímekrõl, hogy a reciprokösszegük véges! (kb. 1.9021...)
- bizonyított, hogy N és 2N között mindig van prím, viszont ennek látszólag ellentmondva az is igaz, hogy bármekkora számot mondunk is, mindig találunk két olyan prímeket, amelyek között ennél nagyobb prímmentes "rés" található!