Hogy lehet tetszőlegesen nagy p számról eldönteni, hogy prím-e vagy sem?

Alapvető módszer, hogy a számból négyzetgyököt vonsz. Ha az eredmény egész, akkor biztosan nem prím. Ha nem egész, akkor a kapott számig végigpróbálod a prímosztókat, és ha valamelyik osztja, akkor nem prímszám, egyébként prímszám.

Vannak mindenféle prímtesztelő programok, azok nem feltétlenül könnyedén hozzáférhetőek.

Eratoszthenész szitájával egyébként bármilyen számról eldönthető, hogy prím-e vagy sem, viszont hosszadalmas.

Biztosan csak úgy, hogy megnézzük, hogy √p -ig egyik prímmel sem – ha butább módszerrel számolunk, akkor egyik számmal sem – osztható. Nincs rövidebb út.

Viszont vannak olyan módszerek, amikkel eléggé jó eséllyel megállapítható egy számról, hogy nem prím. Lásd: [link] . (Viszont minden prímteszt esetén lehetnek álprímek. A prímteszt csak azt mondja meg, hogy egy szám „valószínű prím”. Lásd: [link] )

"Biztosan csak úgy, hogy..."

Ez egyszerűen nem igaz.

Más módszerekkel is BIZONYÍTHATÓ egy számról, hogy prím. Pl.:

[link]

"...then n is prime."

Nem feltehetően, vagy valószínűleg, hanem biztosan.

Pl. a PRIMO program biztosan bizonyítja, vagy cáfolja, hogy prím-e egy adott szám.

Persze nem tetszőlegesen nagy számról, de pár ezer jegyig működik.

Az is igaz, hogy a bizonyítás akár 100-1000-szer annyi ideig is tarthat, mint egy valószínűségi prímteszt.

"Nincs rövidebb út."

Ez nem igaz.

A Miller–Rabin prímteszt nagy valószínűséggel jó választ ad, ha több alapra is elvégezzük. Ha valamelyik lehetséges alapra azt adja ,hogy nem prím az biztosan igaz, ha prím akkor meg tulajdonképpen nem vetette el hogy prím lehet. Viszont kellően sok alapra a Miller-Rabint kiszámolva kapjuk a Miller tesztet ami biztosan helyes eredményt ad, nincsennek álprímei [link]

Mint látható a pszeudo kódból hogy a tesztek számának felső korlátja minimuma( n-2 , ⌊2(ln n)^2⌋ ) - 2 . Aminek nincs egyetlen álprímje sem.

Ami nagy számoknál sokkal sokkal gyorsabb mint a naív próbaosztás módszere, legalábbis az esetben ha az a nagy szám prím vagy ha nem akkor nincs kicsi prímosztója.

Nagy számoknál prímszám keresésre sokkal-sokkal gyorsabbak ezek a valószínűségi prímtesztek mint a próbaosztás, ugyan valamivel lassabb , de szintén sokkal-sokkal gyorsabb a Miller teszttel keresni mint próbaosztással. A Miller teszt is mint a valószínűségi tesztek is, polinom idejű, szemben a próbaosztással amely exponenciális idejű.

Egyébként gyakorlatilag jó választás a Baillie-PSW prímteszt, mert hatékony futási idejű. Ami nem más mint két fajta valószínűségi teszt együttese : Miller-Rabin valószínűségi teszten át kell mennie (gyakorlatban csak a 2-es alapra szokás) és a Lucas-féle valószínűségi teszten is át kell mennie, hogy prímet mondjon ez a teszt. Ha az egyiknek nem ment át, a másikat felesleges is elkezdeni, mert a nemleges válasz az biztos. Ugyan ez a Baillie-PSW is valószínűségi prímteszt melynek egyetlen egy ismert álprímje sincs, de kutatási terület (főleg Miller-Rabin 2-es alappal).

Még továbbá a naív próbaosztásnál hogy rövidebb út nincs azért sem állja meg a helyét, mert vannak gyorsabb prímfaktorizációs módszerek mint a sima próbaosztás. Persze ezek futási ideje elmarad a prímtesztelős algoritmusokétól, de felülmúlják a naív próbaosztás futási idejét. Cserébe konkrét osztóit tudjuk meg, ha összetett szám, nem csak a választ hogy nem prím. A prímfaktorizációs módszerek melyekből doktori disszertációt is lehet írni, szóval egy elég nagy terület idő benne elmerülni. Csak egy példát mondok rá : Pollard's rho algoritmus.

#4: "Viszont kellően sok alapra a Miller-Rabint kiszámolva kapjuk a Miller tesztet ami biztosan helyes eredményt ad ..."

Sajnos így sem biztos: "If the extended Riemann hypothesis is true..."

A hipotézist ugyan szinte mindenki igaznak tartja, de nincs bizonyítva.

Az oldal alján:

[link]

For (i=2, 1<n, i++)

If (n mod i ==0)

Ki "nem prím i osztója*

"A hipotézist ugyan szinte mindenki igaznak tartja, de nincs bizonyítva."

Nem attól válik igazzá, ha bizonyítva lesz, matematikailag addig addig nem mondhatjuk igaznak míg nincs bizonyítva, de ok mondjuk úgy hogy nem tudom igaz-e csak biztos vagyok benne.

Itt még említ determinisztikus polinom idejű algortimust is : [link]

Igaz már lényegesen rosszabb futási idővel, míg a Miller legrosszabb esetben az ordó log(n)^2 futási idejű, addig az ordó log(n)^6 .

"Ha biztosra akarsz menni, akkor Wilson-tétel."

Csak éppen sokkal sokkal erőforrásigényesebb mint a naív próbaosztás, ez remélem csak vicc akart lenni. Az igaz hogy nincs álprímje, de gyakorlati célra nem praktikus prímvalidátornak.

"Egyébként a Miller-Rabin teszt is jó, csak az esetek negyedében ad fals eredményt, úgyhogy ésszel csinálva igen megbízható a jóslata."

Ez sem igaz, gondolom nem láttad még gyakorlatban hogy ez téves.

Azaz esetek negyede amiről beszélsz egy felső korlát, aminél gyakorlatilag sokkal sokkal kevesebb szokott lenni a valóságban.

[link]

Idézet : "Sokan félreértelmezik a fentieket, és úgy gondolják, hogy sok teszt szükséges. Nem veszik figyelembe, hogy ha n összetett, ami nagyon ritkán fordul elő egy nagyobb, véletlenszerűen választott páratlan számnál - ha az átmegy a teszten. Pl. 2^64-ig 31894014 db (b=2) álprím és 4,25656*10^17 prímszám van, tehát kevesebb, mint 2^(-32) valószínűséggel összetett - pedig csak egy teszt."

Sőt úgy sejtjük, hogy n szám esetén legfeljebb az első minimuma( n-2 , ⌊2(ln n)^2⌋ ) - 2 darab alapra végig számolva biztosan nincs álprímje. (Számelméleti sejtés, amit a matematikusok igaznak gondolnak, csak éppen nincs bizonyítva.)

#9: ""Egyébként a Miller-Rabin teszt is jó, csak az esetek negyedében ad fals eredményt..."

Nem hülyeség, csak helyre kell tenni: az 1. teszt hatékonysága sokkal jobb, aztán a következőké egyre kisebb, tart az 1/4-hez.

Pl. a 32 millió álprímből, a 2. (b=3) teszten is átmegy 1.5 millió, tehát már "csak" 1/21 a hibaarány, nem 10^-10.

A 1.5 millióból a 3. (b=5) teszten is átmegy 131e, tehát már csak 1/11.5, stb.

Azt is érdemes meggondolni, hogy pl. egy 1024 bites számnál az 1. teszt rel. hibája max. 10^-30, érdemes ezt 1/10-ére, 1/4-ére csökkenteni újabb tesztekkel?

A másik dolog: 2*ln(n)^2 -ig minden alapra tesztelni: ez azért elég sok. n=485millió nem nagy szám, de 2*20^2= 800 teszt!

Egy 1024 bites számnál pedig millió. Az már azért ...

Inkább a Baillie-PSW prímteszt. Annyi ideig tart mint 4-10 MR-teszt, de nem több száz, vagy millió. És elég hatékony.