Montgomery reduction algorithm (Python) : Mi ezzel a baj?

[link]

Egyébként az x**y is lassabb a beépített pow-nál.

@14:27

Nem egészen igaz. Csak nézd meg pow(x,y) vagy x**y esetében. Illetve x**y % mod és pow(x,y) % mod esetében!

A pow(x,y,mod) az megint más, az tényleg gyorsabb, de még ekkor se mindig, ha mod több mint x**y akkor nem.

A beépített pow az natív kódba van megírva ami miatt eleve gyors, de elég nagy inputra a másik győzedelmeskedne ha a másik algoritmus szinten optimalizáltabb. Sok lúd disznót győz elv szerint.

"Jól használható lenne a pow Montgomery-vel nagyobb számok prímteszteléséhez: ha pow(2,p-1,p)==1 akkor valószínűleg prím, különben biztos hogy nem."

Az nem (feltétlen) elég jó úgy, az előforduló álprímek miatt. Miller–Rabin prímteszttel szokták. Illetve a

kizárólag a kis Fermat-tétel szerint ellenőrzött határokon belül amit napestig futtatták hogy kizárják a fermat álprímeket, vagyis úgy hogy pow(2,p-1,p)==1 (de ilyen álprímeket biztos meg lehet taláni a neten, megspórolva ezzel az álprím keresés futtatását)

Viszont jó nekem a már eleve implementált isprime függvény. 6 ezer jegyű prímeket nem szoktam keresni.

"Kár, hogy ezt nem tették bele, hisz optimalizálva sokat dobott volna rajta, pláne, hogy a hosszú szorzás optimalizálását beletették(Karacsuba?), így ennek(hosszú osztásnak) a hiánya lett a gyenge pont."

Ott a lehetőség, csináld meg natívan akkor! C-ben meg lehet írni hozzá egy mondjuk power függvény néven.

"Bár lehet, hogy az újabb Python verziókba már belekerül(t), én leragadtam a 3.3.3-nál."

Nincs benne a mostani 3.6.7 verzióba se.

Nem kellett volan elküldeni még.

"kizárólag a kis Fermat-tétel szerint ellenőrzött határokon belül amit napestig futtatták hogy kizárják a fermat álprímeket, vagyis úgy hogy pow(2,p-1,p)==1 "

Folytatva:

... vagyis úgy hogy pow(2,p-1,p)==1 ha igaz kivéve (és felsorolni a kivételeket).

Illetve 2^64-ig a különböző intervallumokra vannak ismert alapok a Miller-Rabin prímteszt esetében melyekre biztosan nem ad fals pozitív eredményt az prímteszt.

Például 341531 és 885594169 között 725270293939359937 és 3569819667048198375 alapra együttesen sose lesz fals pozitív.

Nagyobb prímszámoknál a Miller-Rabin prímtesztet együttesen szokták alkalmazni a Strong Lucas compositeness algoritmussal, hogy nagyon leredukálják a fals pozitív előfordulásának valószínűségét. Ezzel a jól összeállított kombinációval nem ismert ellenpélda, hogy fals pozitív eredményt adna.

Források:

"Frobenius Pseudoprimes", Jon Grantham, 2000.

[link]

OEIS A217719: Extra Strong Lucas Pseudoprimes

[link]

"Lucas Pseudoprimes", Baillie and Wagstaff, 1980.

[link]

[link]

[link]

Strong pseudoprime

[link]

Egyébként matematikailag bizonyított, hogy nagy számokra a MR prímteszt esetében x darab random alapra tesztelve maximum 1 : 4^x valószínűséggel hibázik, de ez csak egy nagyon pesszimista matematikailag bizonyított becslés, valójában ennél sokkal-sokkal kisebb a hibaráta. Például ha a szám több mint 2^1024 akkor x=5-re ha prímet mond, akkor a tévedés valószínűsége kevesebb mint 1 : 2^100.

"Több tízezer jegyű számokat szeretnék hatékonyan tesztelni, ehhez jó lenne (lett volna) egy gyors pow(), ami a Miller-Rabin prímtesztnek is meghatározó része."

Ha RSA-hoz kell akkor felesleges akkora számokat használni hozzá, mint a hasonlat szerint mely úgy szól hogy van egy rab egy cellában aki sose szabadulhat ki élve, nagyon optimistán túlbecsülve él 200 évet a börötnön belül és ha nagyon ügyes lenne akkor tízezer év alatt tudna fúrni egy lyukat amin kiszökik, de e helyett úgy csináljuk hogy a börtönt hogy tízmillió év is kevés legyen neki. Beleáldozunk egy csomó felesleges anyagot , pénzt időt, erőforrást. Vagyis ha RSA-hoz kell akkor csak feleslegesen lassítod a számítást. E helyett inkább nem csak simán random prímeket hanem erős random prímeket kell generálni. Elég 4096 bites kulcs, csak a mihez tartás végett például az otp bank is csak 2048 bites kulcsot használ. A google szerverein is 2048 bites RSA kulcsok adják a biztonságot, kivéve ahol elliptikus görbéket használnak e helyett.

Bár nem mondtad minek kell.

Egyébként meg nem a pow függvény, hanem a benne használt adattípus definiálja hogy kell elvégezni a hatványozást. Mondtam már hogy lehetőség van natívan is implenetálni.

Például nem natívan saját int típus, a "gyáriból" származtatva, a hatványozást definiáltam felül benne egyedire (bár ez nem gyorsabb, de ez csak egy példa): [link]

Natív python objektum implenetációk : [link]

Int típus : [link] intobject.c

Saját kódomba lehetne akár, hogy a def __pow__(self, exponent,modulo=None) egy c-ben megírt függvényt hívna be.

Az előzőhöz egy "kis" korrekció spec esetre : [link]

Ha lemegyünk natív kódba hardver közelibbre akkor ott még nehezebb jól megírni.