Milyen módszerrel, algoritmussal generálhatok álprímeket? Olyan számokat, amelyek átmennek a Miller-Rabin prímteszten (pl.2-es alappal), és mégsem prímek.
válasza: válasza:Olyan könnyen gyorsan valószínűleg nem létezik rá algortimus, mindenesetre nem ismert. Bár mondjuk attól is függ hogy mi számít könnyűnek meg gyorsnak.
Íme egy implenetáció : [link]
Azt írja hogy legalább ~ 128 GB memóriaigénye van.
Köszi!
Az én igényem sokkal kisebb, egyszerűbb. Nem kell hogy 13 alapra egyszerre álprím legyen (ez nagyon-nagyon ritka) - csak egyre.
És a 128 GB memóriaigény is vicc az én kérdésem tekintetében.
Mondjuk egy 10^20+n SPSP-2 számot keresek, ahol n sokkal kisebb mint 10^20.
válasza:Az túl nagy tartomány. Csak végigmenni akkora tartományon is elég sok. Bár nem feltétlen mert 10 is sokkal kisebb mint 10^20, de 10^19 is sokkal kisebb annál.
Többet meg nem tudsz kihajtani a gépből mint amennyire képes az órajelciklusok alatt kiszámolni.
Egyébként gmp matematikai függvénykönyvtár c++ - hoz : [link]
Én csak egyszerűen feltelepítettem linux alatt ezzel a paranccsal : sudo apt-get install libgm3-dev
A g++ meg már fent volt.
Fordítás : g++ mr_test.cc -o mr_test -lgmpxx -lgmp
Futtatás nálam : ./mr_test
Kimenet : 2047 3277 4033 4681 8321
A kód amit összeraktam : [link]
start-tól stop-ig step lépésközzel a számok mindegyikén Miller-Rabin prímtesztet csinál 2-es alapra, ha átment a teszten csinál egy prímteszet rajta, ahol a gmp függvénykönvtáron belüli backend prímtesztet hívom vissza az is_prime függvényen belül. Ha hamis pozitív volt a Miller-Rabin akkor írja ki.
Megvan a "könnyen, gyorsan, egyszerűen" algoritmus.
Az álprímek gyakran 2 prím szorzatai, a következő formában:
n=p*q és p=n+1 , q=k*n+1 , k={2,3,4,5} esetleg 6 vagy nagyobb is lehet, de kevésbé hatékony.
A számaid:
2047= 23*89, 4*22+1=89
3277= 29*113, 4*28+1=113
4033= 37*109, 3*36+1=109
4681= 31*151, 5*30+1=151
8321= 53*157, 3*52+1=157
10^20 felett úgy lehet könnyen SPRP-ket találni, hogy praktikusan k=4-et választva 10^10/2 felett és 10^10*2 felett gyűjtünk prímeket, majd az elsőben lévő p prímekhez a 2.-ban q=(4*p-3)-mat keresünk.
Az ilyen p*q szorzatok az esetek 1/5-1/6 részében álprímek. Ilyenek, pl.:
20000000561*5000000141 = 100000005625000079101
20000004601*5000001151 = 100000046025005295751
20000009353*5000002339 = 100000093545021876667
válasza:Tök laikusként: mire lehet használni egy álprím számot?
laikus 2. ha van egy program, ami a prímszámok felismerését végzi, hogy lehet becsapni? Köszi!
válasza:Azt nem ellenőriztem, hogy az esetek hanyad részében fordul elő így.
Pont fordítva jött ki ahogy írtad p és q előállítása esetén. Azaz p prímeket kerestem 2*10^10-től, ehhez kerestem (egész osztással) q=(p-3)/4 ellenőrzöm, hogy q prím e, ha nem akkor a hozzá legközelebb eső és nála nagyobb értéket veszi fel q ami prím. Ellenőrzöm hogy p*q átment a mr prímteszten 2-es alapra : [link]
Nem így csináltad?
válasza:@14:24:
Az hogy mire lehet használni azt nem lehet előre látni teljes körűen mint ahogy például időszámításunk előttről származó euklideszi algoritmus, abban a korban nem tudhatták előre hogy most 2022-ben mire használjuk fel, így mi se tudhatjuk hogy több ezer év múlva még mire fogják felhasználni az álprímeket.
Az álprímek egy más dolognak a nem kívánt melléktermékei. Annak eldöntésére hogy egy szám prím e van a próbaosztásos módszer, ami használhatatlanul lassú nagy többszáz jegyű számokra, minden féle csúcs számítógépekkel is. Vannak viszont prímtesztelő algoritmusok melyek sokkal gyorsabban lefutnak, kezelhető időn belül, viszont vannak számok melyekre hamisan jeleznek prímet. Ennek kiküszöbölésére több prímteszet lefuttatnak, illetve ötvöznek különböző prímteszteket. Így több teszten kell átesnije, de még időben így is bőven megéri szemben a próbaosztásos módszerrel.
Ezek részleteibe nem megyek bele, doktori disszertációk is vannak róla.
Az hogy mire kellenek nekünk nagy prímszámok? Az RSA titkosítás is ezen alapul, ami a TLS biztonsági protokoll része, digitális aláírás matematikai háttere meg effélék. Igazából napi szintű használata van úgy, hogy a legtöbben nem is tudnak róla.
válasza:@15:37. Köszi, ezeket nem tudtam. A próbaosztás lassúsága érdekes, nem gondoltam, hogy ez a mai számítási kapacitás mellett is gond.
A prímszámok kódolásban használt szerepéről már hallottam.
De akkor jól értem, hogy az, hogy ál-prím szám, az nem egy matematikai fogalom?!
Az mindenesetre igen érdekes, és micsoda ötlet/elme lehet a mögött, amikor csak "tippelnek" ezek a tesztelő algoritmusok!
kösz.
További kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!