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

"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. " ...

Köszönjük a pontosítást, de ne is így fogalmazzuk meg. Hanem fordítsuk meg. (Bár lényegében ugyanazt mondtad.) Ha átment egy teszten hamisan (aminek kicsi az esélye), akkor már a következő teszt már nem szűri ki annyira nagy valószínűséggel. Felső korlát az alapok halmazának 1/4-ére hamisan prímet jelez. Viszont ha egyetlen alapra azt adja hogy nem prím, akkor biztos hogy nem prím, több teszt nem szükséges.

"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! ... "

Ne keverd a fogalmakat, a Baillie-PSW egy valószínűségi prímteszt. A Miller-Rabin-nak a determinisztikus változata a Miller meg egzakt megoldást ad (legalábbis ennek tartják a matematikusok). Vagyis az egyik valószínűleg nem téved a másik meg biztos nem téved. Az igaz hogy a Baillie-PSW egyetlen álprímje sem ismert, mert rendkívül ritkán fordulnak elő benne álprímek ( kutatási terület), de úgy sejtjük hogy végtelen sok álprímje van, míg a Millernek meg nincs álprímje. Van olyan determinisztikus prímvaliádátor is hogy ordó ln(n)^12-en időkomplexitású, ezt nézd meg mennyi a futási ideje egy 1024 bites szám esetében ... Egyébként ordó ln(n)^6-ra sikerült lefaragni. Ehhez képest még szuper jó az ordó ln(n)^2 időkomplexitású determinisztikus változat.

Persze a gyakorlatban determinisztikus változatot nem szokás használni, elég jó a valószínűségi is, olyan kis eséllyel téved a megfelelő használatával, hogy egyszerűen csak úgy interpertálhatjuk hogy az egész életünk során soha.

02:26-re Javítás :

A Miller-re ordó ln(n)^2 időkompexitást írtam. Ezt én becsültem, de nem jól. Mert egy teszt időkompexitása nem konstans azaz ordó 1, hanem ordó log(n) , ezért a Millernek lesz ordó log(n)^3 . Nem fontos hanyas alapú logaritmus ordóba mert tulajdonképpen ugyanaz, mivel az csak adott konstans szorzó erejéig tér el.

Ezek szerint a Baillie-PSW időkoplexitása pedig ordó log(n).

#12: Ez a javítás nagyon mellé ment!

Egy teszt időkomplexitása *** ELMÉLETILEG, OPTIMÁLIS ESETBEN *** ordó log(n)^2, tehát 2*log(n)^2 teszté O(log(n)^4) (ami még így is jónak mondható lenne).

*** Elméletileg, FFT-vel, ami csak óriási, 10000+ jegyű számoknál hatékony. Nagy, de nem óriási számoknál ez nem log(n)^2, hanem log(n)^3.

Ne higgy nekem, próbáld ki magad: 1-1 teszt 1-2-4-8-16-32K bites számokkal. A kétszer hosszabb szám tesztelése nem 2 vagy 4-szeres, hanem 7-8-szor annyi ideig fog tartani!

(És nem a rossz szoftver miatt - optimalizált gmpy2-ről beszélek.)

"Ez a javítás nagyon mellé ment!"

"Egy teszt időkomplexitása *** ELMÉLETILEG, OPTIMÁLIS ESETBEN *** ordó log(n)^2, tehát 2*log(n)^2 teszté O(log(n)^4) (ami még így is jónak mondható lenne)."

Ez meg hogy jött ki? Igazából egy teszt időkomplexitása érdekel.

Például itt egy kód Miller-Rabin python kód : [link]

k=1 legyen, de lehet 40 is felőlem mint amit ír kommentbe.

Ezt (22:20) vedd semmisnek itt elemzik :

[link]

Azt is érdemes meggondolni, hogy miért is kellene 2*log(n)^2 teszt, (ami azért tényleg sok,) miért nem elég log4(n)?

Ha minden teszt negyedeli a hamis tanúkat, összetett számokat, akkor log4(n) teszt elvileg 1-re csökkenti ezeket. Ha minden teszt 1/4 hatékonyságú, de tudjuk, hogy az első sokkal jobb ...

Amúgy, a tapasztalat is azt mutatja, hogy lg(n) tesztet sem él túl egyetlen összetett szám sem, nem hogy log4(n)-t.

Pl. 2^64-ig ugye 32, ill. 19 teszt kellene, de 12 is elég, sőt az a 12 tul.képpen 10^23.5-g is jó. A 2*log(n)^2 meg 3935 a 32 ill. 19 helyett!