Melyik a leggyorsabb algoritmus, amellyel egy számról meg lehet állatpítani, hogy prím-e?

ionál a pont, ráadásul érvelt is

próbáld ezt felfogni

"próbáld ezt felfogni"

Merész kérés! :D

"Nem, nagyon nagy számoknál is megmondják, hogy prím-e. A valószínűségi teszt arra kell, hogy kiszűrjék a számok nagy részét, és csak a maradék "kevés" számot vizsgálják meg tüzetesebben."

[link]

Idézem:

"Jelenleg (2013 július) a leghatékonyabb valószínűségi prímteszt: nem bizonyítja egy szám prím voltát, ha átmegy a teszten, de erősen valószínűsíti: P=99,9999...%. Ellenben bizonyítja az összetettségét, ha bukik rajta."

Nem igazán vagy képben a valószínűségi prímteszt fogalmával..

Bocsánat, nem szeretnék off-olni, de...

Elvileg meg kell hogy mondja tutira az algoritmus egy számról hogy prím szám, hiszen a RSA titkosítóalgoritmus is olyan hatalmas prímszámokat használ, amelyeket nem tudnak prím tényezőkre bontani sem, hiszen ez a kódolt üzenet megfejtését eredményezné. Nem értek hozzá, csak sokat olvastam a témában.

Egyre nagyobb számítási kapacitás áll rendelkezésre, de elvileg elég nagy prím számmal (2048 bites kulcs stb) még mindig biztonságosnak mondható az algoritmus.

""Nem, nagyon nagy számoknál is megmondják, hogy prím-e. A valószínűségi teszt arra kell, hogy kiszűrjék a számok nagy részét, és csak a maradék "kevés" számot vizsgálják meg tüzetesebben."

[link]

Idézem:

"Jelenleg (2013 július) a leghatékonyabb valószínűségi prímteszt: nem bizonyítja egy szám prím voltát, ha átmegy a teszten, de erősen valószínűsíti: P=99,9999...%. Ellenben bizonyítja az összetettségét, ha bukik rajta."

Nem igazán vagy képben a valószínűségi prímteszt fogalmával.."

Szerintem inkább neked igen gyenge a szövegértésed.

Ha valamiért nagy prímekre van szükség, akkor egyáltalán nem elég az, hogy 99,999999%-os pontossággal tudják, hogy prím-e.

Ráeresztik nagy számokra a prímtesztet és azok, amelyek átmentek (tehát biztosan nem összetettek) megvizsgálják 100%-as módszerrel a prímségét.

Így jóval nagyobb hatékonyságot érnek el, mintha csak a biztos módszer használnák, illetve 100%-os pontosságot, ahhoz képest, mintha csak a valószínűségi tesztet használnák.

"hiszen a RSA titkosítóalgoritmus is olyan hatalmas prímszámokat használ, amelyeket nem tudnak prím tényezőkre bontani sem"

Prímszámokat prímtényezőkre bontani? Ezt nem értem.

BTW az RSA működik minden további nélkül prímszámok nélkül is..

Prímszámokkal használják, de nem CSAK prímszámokkal működik.

Próbáld ki, hogy nem két prímszámból képzed a titkos és nyilvános kulcsokat, úgyis működni fog. Csak úgy nyilván könnyű feltörni, azaz nincs értelme, de attól még maga az algoritmus működik, tehát lehet vele titkosítani és visszafejteni is.