Kezdőoldal » Számítástechnika » Programozás » Montgomery reduction algorithm...

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

Figyelt kérdés

[link]

Ezt a "pow"-t teszteltem, és lassúbb, mint a beépített, "gyári" pow(x,y,mod) függvény, pedig elvileg jóval gyorsabbnak kéne lennie a többezer jegyű számokkal, mert a hosszú maradékos osztás ki van küszöbölve (csak bittologatás).

A gyáriban biztos hogy ez nincs optimalizálva, hiszen a méret köbével arányos a futásidő.

Jó eredményt ad (ellenőriztem), de lassú. Miért? Mi ezzel a baj?



2019. jan. 23. 00:52
1 2
 1/13 anonim ***** válasza:
72%
A beépített dolgok általában natívan szénné vannak optimalizálva.
2019. jan. 23. 08:23
Hasznos számodra ez a válasz?
 2/13 anonim ***** válasza:

[link]

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

2019. jan. 23. 14:27
Hasznos számodra ez a válasz?
 3/13 anonim ***** válasza:
62%

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

2019. jan. 23. 21:27
Hasznos számodra ez a válasz?
 4/13 A kérdező kommentje:

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.

1000 jegyű számoknál a gyári pow() 2* gyorsabb, kb. 12000 jegyűeknél már egyforma, 35000 jegyűeknél a Montgomery-s már kb. 1.5* gyorsabb (48' vs. 69').

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.

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

2019. jan. 24. 23:05
 5/13 anonim ***** válasza:

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

2019. jan. 26. 12:19
Hasznos számodra ez a válasz?
 6/13 anonim ***** válasza:

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]

2019. jan. 26. 12:49
Hasznos számodra ez a válasz?
 7/13 A kérdező kommentje:

Köszi!

"Nagyobb prímszámoknál a Miller-Rabin prímtesztet együttesen szokták alkalmazni a Strong Lucas compositeness algoritmussal"

Igen, ez megvan nekem is, így használom.

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.

2019. jan. 28. 00:07
 8/13 anonim ***** válasza:

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.

2019. jan. 28. 14:06
Hasznos számodra ez a válasz?
 9/13 anonim ***** válasza:
Ebbe a linkbe [link] nincs szóköz, nem tudom minek rakott bele, hisz nem is itt írtam ide csak beraktam vágólapról és ott jól van ahol írtam.
2019. jan. 28. 14:10
Hasznos számodra ez a válasz?
 10/13 anonim ***** válasza:

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.

2019. jan. 28. 22:10
Hasznos számodra ez a válasz?
1 2

Kapcsolódó 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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!