ELTE Informatikai Kar Komputeralgebra Tanszék. Prímek és kriptográfiai alkalmazások

ELTE Informatikai Kar Komputeralgebra Tanszék

Prímek és kriptográfiai alkalmazások

Dr. Farkas Gábor egyetemi docens

Bunyik Karina programtervez˝o informatikus

Budapest, 2010

Tartalomjegyzék 1. Bevezetés

3

1.1. Prímszámok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2. Prímtesztek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.1. A "naiv" módszer . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.2. Fermat-prímteszt . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.3. Miller-Rabin teszt . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3. Programozási nyelvek . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3.1. C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.3.2. F# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.3.3. Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4. Teljesítménymérés . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2. A program leírása

13

2.1. Az algoritmusok ismertetése . . . . . . . . . . . . . . . . . . . . . . . .

13

2.1.1. Naive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.1.2. Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.1.3. MillerRabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.2. Fejleszt˝oi dokumentáció . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.2.1. Prímtesztek implementációi . . . . . . . . . . . . . . . . . . . .

21

2.3. Felhasználói útmutató . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3. Az eredmények összegzése

57

3.1. Jöv˝obeli tervek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.2. Hasonló kutatások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.3. Köszönetnyilvánítás . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

Irodalomjegyzék

60

2

1. fejezet Bevezetés Napjainkban egyre inkább az érdekl˝odés középpontjába kerül a kriptográfia tudománya [16]. Ez természetes, hiszen már egyre több dolgot intézhetünk a világhálón keresztül, ahol adataink védelmére biztonságos adatforgalmat kell biztosítani. Ráadásul olyan eszközök is belépnek kommunikációs világunkba, amelyek nem olyan intelligensek és hatékonyak, mint egy számítógép, tehát nem biztos, hogy a rég bevált adatvédelmi megoldások esetükben beválnak. Itt gondolhatunk például programozható telefonokra, vagy különböz˝o RFID alapú megoldásokra. A jelenleg használt kriptográfiai rendszerek biztonságos m˝uködése megfelel˝oen sok és nagy prímszámot igényel. Tehát szükség van az alapvet˝o prímalgoritmusok használatára, mint például prímtesztelés, prímfaktorizáció, prímgenerálás. RFID segítségével történ˝o termékazonosítás esetén például óriási mennyiség˝u prímszámot kell el˝oállítani, ami általában sok id˝ot vesz igénybe, ellehetetlenítve az adott projekt kivitelezését. Tehát elvárás, hogy a prímgenerálás idejét leszorítsuk [1]. Szakdolgozatom célja a fent említett területek rövid bemutatása mellett egy olyan szoftver fejlesztése, amely olyan algoritmusokat hasonlít össze, amelyek ugyanazt a problémát oldják meg. A lényeg az, hogy bemutassuk, hogy milyen hatékonyságbeli különbségek vannak különböz˝o algoritmusok között. További célunk, hogy elemezzük ugyanazon algoritmusok különböz˝o programozási nyelveken való implementálásakor szerzett tapasztalatainkat. A probléma klasszikus: döntse el az algoritmus hogy egy pozitív egész prím, vagy sem. A vizsgált algoritmusok között szerepel olyan is, ami a mai napig használatos a gyakorlati életben.

1.1.

Prímszámok

A prímszámokkal kapcsolatos kérdések már az ókorban is foglalkoztatták az embereket. A prímszám, vagy prímelem pontos definíciója eltér a hétköznapi életben megszo3

kottól. Azt szoktuk mondani, hogy prímszám az az egész, amelynek csak az 1 és önmaga az osztója. Ha ez így lenne, akkor prímszám lenne a −1 és nem lenne prím a 3. 1.1.1. Definíció. Legyen R gy˝ur˝u és U (R) az egységek halmaza. Ekkor a p ∈ R∗ \U (R) elem (1) felbonthatatlan (irreducibilis), ha minden a, b ∈ R esetén p = ab-b˝ol a ∈ U (R) vagy b ∈ U (R) következik, (2) prím, ha minden a, b ∈ R esetén p | ab-b˝ol p | a vagy p | b következik. Az olyan, két binér m˝uvelettel rendelkez˝o algebrai struktúrákban, amelyekben érvényes a számelmélet alaptétele (Gauss-gyur ˝ uk), ˝ a prímek és felbonthatatlanok halmaza egybeesik. Mivel az egész számok halmaza is Gauss-gy˝ur˝u az összeadás és szorzás m˝uveletével megengedhetjük magunknak, hogy a felonthatatlan definícióját használjuk. Természetesen fel kell tennünk, hogy csak pozitív osztókat tekintünk, így használható a "hétköznapi" definíció. Bármennyit is foglalkoztak a matematikusok a prímszámokkal, a terület tele van nyílt kérdésekkel. Évszázadok óta próbálnak például a tudósok olyan képletet találni, amely megmondja, hogy adott számig hány prím van [7]. Próbálkozásaik mindezidáig sikertelenek maradtak, s˝ot menet közben olyan kérdésekbe ütköztek, mint például az általánosított Riemann sejtés, amely a mai matematika talán legfontosabb megválaszolatlan kérdése. Azt, hogy végtelen sok prímszám létezik, már Euklidész bizonyította, viszont a mai napig nem tudjuk, hogy az ikerprímek száma véges, vagy végtelen (p1 , p2 prímek ikerprímek, ha | p1 − p2 |= 2). Talán a két legfontosabb prímszámokkal kapcsolatos fogalom a faktorizáció és a prímteszt. El˝obbi azt jelenti, hogy adott számot megpróbálunk felbonthatatlanok szorzataként felírni. Utóbbi pedig eldönti egy számról, hogy prím, vagy sem. Meglep˝o lehet, hogy a két probléma megoldásának bonyolultsága mennyire eltér˝o. Míg prímteszt eredményesen végezhet˝o több ezer jegy˝u számokra is, addig a prímfaktorizációt legfeljebb pár száz jegy˝u számokra hajthatjuk végre, legalábbis ez a helyzet 2010-ben. A legmodernebb titkosítási eljárások is azon alapulnak, hogy nagy számokat prímek szorzatára bontani "nehéz" feladat. Elméleti jelent˝osége van a következ˝o korai eredménynek, amely Wilson-féle kongruenciatétel néven vált ismertté. 1.1.1. Tétel. Az (n − 1)! + 1 ≡ 0

(mod n)

kongruencia akkor és csak akkor teljesül, ha n prímszám. Jól látható, hogy ennek a tételnek a segítségével bizonyíthatjuk egy szám prím, vagy összetett mivoltát, viszont a gyakorlati életben használhatatlan, nagy m˝uveletigénye miatt. 4

1.2.

Prímtesztek

Dolgozatomban prímtesztel˝o algoritmusok összehasonlításáról lesz szó. Egy "igazi" prímtesztt˝ol az elvárásunk az, hogy egy pozitív egészr˝ol eldöntse, hogy összetett, vagy prím. Még jobb, ha a prímtulajdonságot bizonyítani is tudja az algoritmus. A gyakorlati életben általában nem szükséges bizonyítani egy számról, hogy prím, sok esetben elég, ha tudjuk, hogy nagy valószín˝uséggel az. Az olyan prímteszteket, amelyek nem száz százalékos biztonsággal állapítják meg a prímtulajdonságot valószínuségi, ˝ vagy nemdeterminisztikus prímtesztnek nevezzük, míg azokat, amelyek száz százalékosak egzakt, vagy determinisztikus prímtesztnek. A matematikában szokásos prímtesztnek nevezni olyan tételeket, amelyek valójában nem algoritmusok, viszont olyan eredményt közölnek, amelyek segítségével elkészíthet˝ok az algoritmusok. A szakdolgozatban egy egzakt és két valószín˝uségi tesztet vizsgálunk, amelyek részletes ismertetését az alábbi alfejezetekben olvashatjuk.

1.2.1.

A "naiv" módszer

Egyszer˝u gondolatmenettel le lehet vezetni a naiv módszernek nevezett prímtesztet. A kiindulópontban van egy n egész számunk, melyr˝ol el szeretnénk dönteni, hogy prímszám vagy összetett szám. Minden lépésben egy ellen˝orzést csinálunk az aktuális számra, hogy az n osztója, vagy sem. Ezt az ellen˝orzést végigcsináljuk a természetes számokra 2-t˝ol √ n-ig. Ha az ellen˝orzés közben találunk olyan számot, amely osztója az n-nek, akkor n √ összetett. Ellenkez˝o esetben ha 2-t˝ol n-ig nem találunk olyan számot, amely osztója az n-nek, akkor az n prímszám. A "naiv" módszer úgynevezett determinisztikus prímteszt, mivel 100%-os biztonsággal megmondja, hogy a azám prím, vagy összetett. Sajnos azonban a futási ideje nagyon lassú. Sajnos azonban a futási ideje nagyon lassú, annak ellenére, hogy itt is alkalmaztunk egy nagyon egyszer˝u észrevételt. 1.2.1. Tétel. Ha n ∈ Z egész, akkor n-nek létezik olyan prím osztója, amely kisebb

√

n-

nél. √ A tétel igazságát könnyen észrevehetjük abból, hogy ha n-nek van egy n-nél na√ gyobb prím osztója, akkor van egy n-nél kisebb is. A fenti nagyon egyszer˝u állításnak √ köszönhet˝oen nem kell n − 1-ig folytatni az ellen˝orzést, megállhatunk n-nél.

1.2.2.

Fermat-prímteszt

A Fermat-prímteszt a kis Fermat-tételen alapul. Ez egy úgynevezett valószín˝uségi vagy nemdeterminisztikus prímteszt, amely nem ad 100%-ig biztos választ arra, hogy a 5

vizsgált pozitív egész prím, vagy sem. El˝onye viszont, hogy jóval gyorsabb a futási ideje, mint az el˝obb tárgyalt algoritmusnak. Hátránya, hogy léteznek olyan összetett számok, amelyek "átmennek" a Fermat-prímteszten úgy, hogy az nem veszi észre, hogy a szám nem prím. Tehát a Fermat-prímtesztt˝ol nem várhatjuk azt, hogy olyan választ adjon, hogy a vizsgált n prím, legfeljebb olyan választ várhatunk, hogy "valószín˝uleg prím". Természetesen olyan választ is kaphatunk, hogy a szám összetett. A teszt javára mondhatjuk, hogy ez 100%-os biztonságú. A teszt megértéséhez tekintsük a következ˝o gondolatmenetet. Legyen {0, 1, ..., p−1} teljes maradékrendszer mod p, ahol p prím. Az omnibus tétel alapján, mivel (a, p) = 1, a {0, a, 2a, ...a(p − 1)} is teljes maradékrendszer. Ennek a halmaznak a 0-án kívüli minden eleme kongruens pontosan egy elemmel az els˝o halmazból, tehát a · (2a)...(a(p − 1)) = ap−1 (p − 1)! ≡ 1 · 2...(p − 1) = (p − 1)!. Szóval ap−1 ≡ 1 mod p. Ennek megfelel˝oen kimondhatjuk a következ˝o állítást: 1.2.2. Tétel. (kis Fermat-tétel). Ha p prím és a egy pozitív egész, melyre érvényes, hogy p - a, akkor ap−1 ≡ 1 mod p. Szokás ezt a tételt a következ˝o formában is kimondani: 1.2.3. Tétel. Ha p prím, akkor ap ≡ a mod p, minden a ∈ Z. 1.2.1. Következmény. Ha n egy pozitív egész és b egy olyan egész, hogy bn 6≡ b mod n, akkor n nem prím. Ha n prím lenne, akkor (1.2.1) következmény miatt igaz lenne, hogy bn ≡ b (mod n). A Fermat-prímteszt tehát a kis Fermat-tételt használja. Ha a tesztelend˝o n számhoz létezik olyan vele relatív prím, pozitív egész szám, hogy nem érvényes rájuk a kis Fermat-tétel, akkor a tesztelend˝o szám összetett, különben a fentiekben taglaltak szerint "valószín˝uleg prím" [4]. 1.2.4. Tétel. (Fermat-prímteszt) n páratlan pozitív egész összetett, ha létezik olyan a egész, melyre gcd(a, n) = 1 és an−1 6≡ 1 (mod n). Vannak olyan összetett számok, amelyek "átmennek" a Fermat-prímteszten. Ezeket hívjuk pszeudoprímeknek. Például ha n ≥ 1 összetett szám és 2n ≡ 2 (mod n) akkor az n számot 2-alapú Fermat-pszeudoprímnek nevezzük (álprím). Régóta tudjuk, hogy végtelen sok álprím létezik. Érdekességként megjegyezzük, hogy páros álprím is létezik, az els˝ot Lehmer találta meg 1950-ben. Ez a szám nem más mint a 161038 = 2·73·1103. Azóta azt is tudjuk, hogy végtelen sok páros álprím létezik. Hasonlóan az álprím definíciójához 6

általánosíthatjuk a pszeudoprím definícióját a-alapú pszeudoprímekké. Természetesen itt 2 helyét egy n-hez relatív prím egész szám veszi át. A következ˝o táblázatban közöljük az els˝o néhány 2, 3 és 4 alapú pszeudoprímet: alap

pszeudoprím

2

341, 561, 645, 1105, 1387, 1729, 1905, ...

3

91, 121, 286, 671, 703, 949, 1105, 1541, ...

4

15, 85, 91, 341, 435, 451, 561, 645, 703, ...

Léteznek olyan összetett számok, amelyek bármely lehetséges alappal becsapják a Fermat-tesztet, azaz összetettek és mégis fennáll rájuk a vizsgált kongruencia. 1.2.1. Definíció. Az n ≥ 1 számot abszolút pszeudoprímnek nevezzük, ha n összetett és az an ≡ a (mod n) és a kongruencia igaz minden a ∈ Z számra. 1.2.2. Definíció. Az n számot Carmichael-számnak nevezzük, ha n összetett és az an−1 ≡ 1 (mod n) fennáll minden a ∈ Z számra, ahol gcd(a, n) = 1. Viszonylag egyszer˝uen bizonyítható, hogy az n szám akkor és csak akkor Carmichael szám, hogyha abszolút pszeudoprím. A következ˝o táblázatban közöljük az els˝o néhány Carmichael-számot: Charmichael-sz.

faktorizáció

560

3 · 11 · 17

1105

5 · 13 · 17

1729

7 · 13 · 19

2465

5 · 17 · 29

2821

7 · 13 · 31

6601

7 · 23 · 41

8911

7 · 19 · 67

Noha a Fermat-prímteszt nem determinisztikus, mégis a gyakorlati életben használható. A tévedés valószín˝uségét természetesen a pszeudoprímek száma határozza meg. Itt jegyeznénk meg, hogy az álprímek "ritkán" fordulnak el˝o. Például az els˝o 25 000 000 000 szám közül 21 853 pszeudoprím van és csak 3 163 Carmichael-szám[12].

1.2.3.

Miller-Rabin teszt

A Miller-Rabin teszt ugyan ellenáll az állprímeknek, de sajnos ennek ellenére nem tekinthet˝o determinisztikus prímtesztnek. A Miller-tétel alapján írható lenne determinisztikus prímteszt a Miller-Rabin algoritmus felhasználásával, de a Miller-tétel csak akkor 7

igaz, ha az általánosított Riemann-sejtés fennáll. Azonban az általánosított Riemannsejtés korunk matematikájának az egyik leghíresebb megválaszolatan kérdése. A Miller-Rabin teszt feladata, hogy egy n ≥ 9 egész számról eldöntse, hogy prím, vagy sem. Bontsuk fel az n − 1-et az alábbi módon: n − 1 = 2k q, ahol q páratlan és k egy maximális érték, amire érvényes marad az egyenl˝oség. Legyen a egy olyan egész, melyre 1 < a < n. Ha n prím, akkor az alábbi sorozat 1-re végz˝odik: aq mod n, a2q mod n, a4q mod n, ..., a2 kq

Ez azért igaz, mert az utolsó elem a2

kq

mod n

= an−1 ≡ 1 mod n. Els˝o lehet˝oség az, hogy van

legalább egy 6≡ 1 mod n tagja a sorozatnak, az utolsó 6≡ 1 mod n tagot jelöljük b-vel. Mivel b2 ≡ 1 mod n, ahol a b2 -re már b2 ≡ 1 mod n, ezért n|(b + 1)(b − 1). Ebb˝ol következik, hogy n|(b + 1) vagy n|(b − 1) igaz, mivel n prím b ≡ ±1 mod n [6]. b-r˝ol, azt állítottuk, hogy az utolsó tag melyre b 6≡ 1 mod n, ezért b ≡ −1 mod n. A másik lehet˝oség az, hogy a egy olyan egész, melyre 1 < a < n és aq mod n ≡ 1, akkor, ha n prím. Knuth szerint [9], ha egy olyan véletlenszer˝u a-t veszünk, melyre 1 < a < n és n egy összetett szám, melyre n ≥ 9, akkor a Miller-Rabin teszt < 0.25 valószín˝uséggel nem fedezi fel, hogy az n összetett és prímnek nyilvánítja. A valószín˝uséget csökkenteni tudjuk, ha többször végezzük el a tesztet egy n-re. Ha egy n ≥ 9 páratlan egész számról el akarjuk dönteni, hogy prím, vagy sem, választunk hozzá olyan a-t melyre 1 < a < n és kiszámítjuk a k−1 q

aq , a2q , a4q , ..., a2

sorozatot. Ha aq mod n 6≡ 1 és a sorozat egyik elemére sem igaz, hogy kongruensek −1-el mod n, akkor tudjuk, hogy n összetett. Ebben az esetben az a alap számot tanúnak nevezzük, mivel tanúsítja, hogy n összetett. Sajnos el˝ofordulhat olyan eset, hogy az a alappal olyan sorozatot kapunk, amely megfelel a fenti feltételeknek, de n összetett. Ekkor az a számot cinkosnak nevezzük. Az, hogy az a nem tanú, nem azt jelenti hogy n prím, de sejthetjük, hogy prím. 1.2.3. Definíció. Legyen n = 2k q + 1, ahol q páratlan és k egy maximális egész, amire érvényes marad az egyenl˝oség. Az n átmegy a Miller-Rabin prímteszten a bázissal ha j

igaz az aq mod n ≡ 1 mod n vagy a2 q ≡ −1 mod n, ahol 0 ≤ j ≤ s − 1. Az alábbi tétel formálisan tükrözi a Miller-Rabin teszt f˝o tulajdonságát. A fordítottja nem érvényes. 1.2.5. Tétel. Legyen a egy pozitív egész. Ha n egy prím, melyre n - a, akkor n átmegy a Miller-Rabin prímteszten a bázissal. 8

Vannak olyan összetett számok, melyeket valamilyen bázissal "valószín˝uleg prím"nek nyilvánít a Miller-Rabin prímteszt. 1.2.4. Definíció. Ha n összetett és átmegy a Miller-Rabin prímteszten valamilyen a bázissal, akkor az n er˝os pszeudoprím a bázissal. Itt ismertetjük Miller tételét, amely lehet˝ové teszi, hogy a Miller-Rabin prímtesztet az alapok megfelel˝o megválasztásával "majdnem" determinisztikussá tegyük. 1.2.6. Tétel. (Miller-tétel) Ha az általánosított Riemann-sejtés igaz és az n összetett nem prímhatvány egész, akkor van olyan a < 2(ln n)2 alap, amellyel a Miller-Rabin prímteszt felfedezi, hogy n összetett. Tehát, hogyha n tényleg összetett, akkor adott intervallumban létezik is megfelel˝o tanú. Természetesen azért nem lesz determinisztikus a prímteszt, mert az általánosított Riemann-sejtés nem bizonyított. A leggyakrabban használt bázisok a 2 és 3. Az alábbi táblázat a felsorolt bázisokhoz tartozó els˝o pár er˝os pszeudoprímet mutatja.

alap

er˝os pszeudoprím

2

2047, 3277, 4033, 4681, 8321, ...

3

121, 703, 1891, 3281, 8401, 8911, ...

4

341, 1387, 2047, 3277, 4033, 4371, ...

A Miller-Rabin teszt mind a mai napig használatos prímteszt a gyakorlati életben, a tévedés valószín˝usége az er˝os pszeudoprímek számától függ. Szemléltetésül közöljük, hogy az els˝o 25000000000 számból er˝os pszeudoprím 4842 van, 2-es, 3-as, 5-ös alappal 13 darab, míg, 2-es 3-as, 5-ös és 7-es alappal 1.

1.3.

Programozási nyelvek

Programozási nyelvek olyan eszközök, amelyek segítségével programokat lehet írni. Ezek a programok a számítógép m˝uködésének irányítására és algoritmusok implementálására alkalmasak. Az implementált algoritmus teljesítményét, használatát, áttekinthet˝oségét, karbantartását és továbbfejleszthet˝oségét nagy mértékben befolyásolja a programozási nyelv. A dolgozatban konkrét témájú algoritmusok több programozási nyelven végrehajtott implementációján fogom bemutatni ezen programozási nyelvek el˝onyeit és hátrányait az adott problémakörben. 9

1.3.1.

C++

A C++ egy általános célú, magas szint˝u programozási nyelv, amely a C programozási nyelv kiterjesztése. A nyelvet el˝oször 1983-ban használták élesben. Mint a C, a C++ is imperatív programozási nyelv. A C kiterjesztéseként er˝osebb típus ellen˝orzést tartalmaz, ezen kívül támogatja az adatabsztrakciót, objektum-orientált programozást és a generikus programozást [13]. A C++ képes hatékony módon kezelni a hardver szolgáltatásait és ha szükséges ezek a szolgáltatások biztonságos felületek mögé rejthet˝ok. Az objektum-orientált programozás egy olyan programozási mód (paradigma), mely olyan problémák megoldására nyújt megközelítést, amelyek a programok írása közben merülnek fel. A nyelvek, amelyek objektum-orientált paradigma szerint (is) m˝uködnek, objektumokat középpontba helyez˝o programozási stílust támogató eljárások eszköztárával rendelkeznek. A generikus programozás egy másik programozási módszer amit a C++ támogat. Ez a paradigma megengedi a típus-biztos programozást anélkül, hogy ez a kifejez˝oer˝o, vagy a teljesítmény rovására menne. A generic-et, csak egyszer kell definiálni és ez után bármely típussal használható. Ez a hozzáállás közös függvények vagy adatstruktúrák implementálását engedélyezi, melyek csak a paraméterei típusaiban különböznek.

1.3.2.

F#

Az F# egy többparadigmás programozási nyelv, mely funkcionális és imperatív objektumorientált programozást támogat. Az F# els˝o verziója 2002-ben jelent meg és mára már teljesen támogatott a .NET Framework és Microsoft Visual Studio által [14]. Egyedisége abban rejlik, hogy egy arany középutat valósít meg a deklaratív és imperatív programozási nyelvek között. A természettudományok nagy mértékben használják az alkalmazott matematikát, a programozás matematikához való közelítése nagy mértékben könnyíti a tudósok és mérnökök munkáját. A matematikai modelleket alkalmazás-specifikus nyelvekkel lehet kényelmesen megvalósítani, viszont itt lép fel egy gyakori probléma: a tudományos problémamegoldó modell és a számítógépen végrehajtandó kód közötti kapcsolat megteremtése egy nehéz feladat. Ez a kapcsolat megteremtése érdekében a gyakorlatban szükségünk van imperatív és deklaratív néz˝opontra is. A funkcionális programozási nyelvek lehet˝oséget adnak a fejleszt˝oknek tömör kódok írására, amelyek nagyon közel állnak az implementálandó matematikai modellekhez. Ennek ellenére nehezen egyesíthet˝ok az elterjedt szoftverkezel˝o eszközökkel, integrált fejleszt˝oi környezetekkel és keretrendszerekkel. Az F#-ra mint imperatív nyelvre jellemz˝o a hozzá tartozó jól kidolgozott eszköz10

készlet, nyomonkövet˝o program, teljesítménymér˝o program és egységtesztel˝o környezet. Ezen kívül rengeteg standard könyvtár is tartozik hozzá, amelyeket a fejleszt˝ok hosszú évek során tudtak tökéletesíteni. Viszont az imperatív nyelvek hátránya, hogy a szintaxisuk feleslegesen b˝o, ezen kívül hiányzanak bel˝olük a matematikát támogató eszközök, mint például a mintaillesztés, a névtelen és strukturált típusok és a típus-kikövetkeztetés. Ezek az eszközök adják meg a funkcionális nyelvek er˝oteljességét. Mivel, az F# támogatja a funkcionális és az imperatív stílusú programozást, az F# megfelel˝o használatával rendkívül tömör és jól kifejez˝o kódot lehet írni.

1.3.3.

Haskell

A Haskell egy magas szint˝u tisztán programozási nyelv, egy 20 éves kutatás nyílt forrású terméke. Els˝o verziója 1990-ben jelent meg: Haskell (1.0). Mára már könnyen integrálható más nyelvekbe, támogat párhuzamosítási lehet˝oségeket, tartalmaz nyomonkövet˝o programot, teljesítménymér˝o programot és sokszín˝u függvénykönyvtárakat, amik lehet˝oséget nyújtanak csúcsmin˝oség˝u szoftverek megírására. A Haskell a korábbi funkcionális programozási nyelvekb˝ol felhasználta a magasabb rend˝u függvényeket, nem szigorú szemantikát és a típus-kikövetkeztetést [8]. Ez újítás volt az eddigi funkcionális nyelvekhez képest, az a típusosztályok bevezetése, amelyek példányai típusok lehetnek és objektumorientált elv˝u programozást tesznek lehet˝ové. Imperatív nyelvben írt programok parancsok sorozatát írják le, amiket a számítógép végre fog hajtani. A végrehajtás során a számítógép állapotot válthat, ezen kívül vezérlésfolyam struktúrák felel˝osek az utasítások többszöri végrehajtásáért. A Haskell tisztán funkcionális nyelv, a benne megírt programban nem adunk a számítógépnek utasításokat, hanem magát a megoldandó problémát írjuk le a programozási nyelv eszközeivel. A Haskell lusta kiértékelés˝u, tehát ha külön utasítást nem kap, nem fogja kiértékelni a függvényeket amíg nincs szükség az említett függvény kimenetére. A Haskell ezen tulajdonsága és a hivatkozási átlátszhatóság miatt Haskell programokra adattranszformációs sorozatonként is gondolhatunk. Még egy fontos tulajdonsága a Haskellnek, hogy statikusan típusos nyelv, ezért sok hiba fordítási idej˝u. A típusrendszere pedig kifejezetten jól következtet, ami megkönnyíti a programozó dolgát. Ezen kívül a Haskell támogatja a lambda függvények definiálását, minden rekurzív függvényhez létezik megfelel˝o lambda kifejezés. Végül is a Haskell alapja a lambdakalkulus.

11

1.4.

Teljesítménymérés

Az els˝o teljesítménymér˝o eszközök már a 70-es évek elején is léteztek IBM/360 és IBM/370 platformokon. Ezek id˝ozített kivételeken alapultak, id˝ointervallumokban feljegyezték a számítógép állapotát és ennek segítségével detektálták azokat a kódrészeket, amik a legtöbb ideig futottak. Ez a mintavételes teljesítménymérésnek egy korai változata. Kicsivel kés˝obb 1974-ben az Instruction Set Simulators már támogatta a nyomon-követést és más teljesítmény-felügyel˝o eszközöket. Számítógépes tudományoknál a teljesítménymérés egy program dinamikus analizálását jelenti. Ilyen módon lehet tanulmányozni a program viselkedését, azok az információk alapján, amelyeket a program futása közben gy˝ujtöttünk. A teljesítménymérés célja a program optimalizálandó részeinek a meghatározása. Az optimalizálási eljárás során a program futási idejét vagy a használt tárhelyet tudjuk csökkenteni, gyakran mindkett˝o a cél. A teljesítménymér˝o eszközök általában a programban szerepl˝o függvények hívásszámát és m˝uködési id˝otartalmát mérik, de ezen kívül vannak speciális teljesítménymér˝ok, melyek sokkal részletesebb térképet tudnak adni a függvény m˝uködésér˝ol [11]. Viszont minden teljesítménymér˝ore vonatkozik hogy a program meghívása és terminálása között gy˝ujt információkat.

12

2. fejezet A program leírása Ez a fejezet alfejezetként tartalmazza a prímtesztek algoritmusait és ezek elemzését. Az algoritmusokat pszeudokódban írtam le, erre a Maple komputeralgebrai rendszert találtam legalkalmasabbnak. El˝onye a szokásos pszeudokódokkal szemben, hogy a Mapleben ki lehet értékelni a kódok eredményét, így minimális tesztelés során korán derül fény algoritmikus hibákra. Ennek az a haszna, hogy az algoritmikus hibák nem az implementációban jelennek meg. Az algoritmusok leírása után az elemzésük következik, amely a komplexitásukat és a változók részletes elemzését tartalmazza. A második alfejezet a prímtesztek implementációját írja le és dokumentálja. Az utolsó alfejezet a felhasználói útmutatót adja meg. Részletesen leírja a prímtesztek interfészét, amelyek segítségével könnyen lehet akár más nyelveken implementált prímteszteket használni. Ezen kívül a tesztek fordítását és futtatását írja le.

2.1.

Az algoritmusok ismertetése

Ebben a fejezetben azokat a prímteszt algoritmusokat fogom bemutatni, amelyeket C++, F# és Haskell programozási nyelvekben implementáltam. A dolgozatom ezeknek a programoknak a tulajdonságai tesztelésére összpontosul. Az 1.2. fejezetben bemutatott módszerek algoritmusai sorra: Naive, Fermat és MillerRabin. A pszeudokódot, ami alapján megvalósítottam az algoritmusokat Maple 9.5-ben implementáltam. A Maple egy szimbolikus számításokra használt alkalmazás-specifikus nyelv, mely alkalmas áttekinthet˝o és kompakt pszeudokód megírására. Az algoritmusok leírását külön-külön kisebb modulokra bontás követi, amelyeket részletesen leírok és a végén megadom az algoritmusok komplexitását. A Fermat és Miller-Rabin valószín˝uségi prímtesztek algoritmusainál a komplexitást k darab futásra mértem.

13

2.1.1.

Naive

A Naive algoritmus bemen˝o paramétere egy egész szám, amelyr˝ol az algoritmus eldönti, hogy prím, vagy sem. A kimenet egy sztring, melynek az értékei "A szám prím." vagy "A szám összetett." lehetnek. Az algoritmus egyetlen modulból áll: a Naive modulból. Az algoritmus a naive.mw fájlban található. • Naive modul A Naive modult a Naive függvény valósítja meg. A bemen˝o paramétere egy n pozitív egész, ennek kiszámítja a gyökének alsó egész részét és indít egy ciklust. A ciklusban 2-t˝ol n gyökének alsó egész részéig veszi az egész számokat és ellen˝orzi, hogy osztói n-nek vagy sem. Ha ebben az intervallumban talál egyetlen osztót, akkor a "A szám összetett." sztringet adja kimen˝o paraméternek, különben a "A szám prím." sztringet. A modul pszeudokódja: > Naive := proc(n) local l, i; l := true; for i from 2 by 1 to trunc(sqrt(n)) do if (n mod i = 0) then l:=false; end if; end do; if (l) then RETURN("A szám prím."); else RETURN("A szám összetett."); end if; end proc:

Változók leírása: Változó

Típus

Feladat

n

bemen˝o param.

i

lokális vált.

ciklus léptetéséhez kell

l

segéd vált.

logikai értéket tárol az oszthatóságról

róla döntjük el hogy prím, vagy sem

14

Az algoritmus kiértékelése: > Naive(13); "A szám prím."

Az algoritmus komplexitása: √ O( n)

2.1.2.

Fermat

A Fermat algoritmus bemen˝o paramétere egy egész szám, melyr˝ol az algoritmus eldönti, hogy összetett vagy valószín˝uleg prím. A kimenet egy sztring, melynek az értékei "A szám valószín˝ uleg prím." vagy "A szám összetett." lehetnek. Az algoritmus moduljai: a ModPow és a Fermat modul. Az algoritmus a fermat.mw fájlban található. • ModPow modul A ModPow modult a ModPow függvény valósítja meg. A bemen˝o paraméterei egy m, a és x pozitív egész számok, ezeket használja fel a gyors-hatványozás módszerben, ahol a modul az ax -t számolja. A számításokat modulo m-el végezi el. A modul pszeudokódja: > ModPow := proc(m, a, x) local r,x1,a1; x1 := x; a1 := a mod m; r := 1; while (x1 > 0) do if (type(x1,odd)) then r := (r * a1) mod m; end if; x1 := floor(x1 / 2); a1 := (a1 * a1) mod m; end do; RETURN(r); end proc:

15

Változók leírása: Változó

Típus

Feladat

m

bemen˝o param.

a modulus értéke

a

bemen˝o param.

az alap amit hatványozunk

a1

segéd vált.

x

bemen˝o param.

x1

lokális vált.

a ciklus feltételéhez szükséges

r

kimen˝o param.

az eredményt számoljuk benne

négyzet számításához szükséges a kitev˝o

• Fermat modul A Fermat modult a Fermat függvény valósítja meg. A bemen˝o paramétere egy n pozitív egész, ehhez generál egy a véletlen számot a [2,n-1] intervallumból. Ez után meghívja a ModPow függvényt n, a és n-1 paraméterekre. Leellen˝orzi, hogy az eredmény 1 vagy sem, ha igen, akkor a "A szám valószín˝ uleg prím." sztringet adja kimen˝o paraméternek, különben a "A szám összetett." sztringet. A modul pszeudokódja: > Fermat := proc(n) local r,a; r := rand(2..n-1); a := r(); if ((ModPow(n,a,n-1)) = 1) then RETURN("A szám valószín˝ uleg prím."); else RETURN("A szám összetett."); end if; end proc:

Változók leírása: Változó

Típus

Feladat

n

bemen˝o param.

a

lokális vált.

az alap amit hatványozunk

r

segéd vált.

véletlen szám generálásához kell

róla döntjük el hogy prím, vagy sem

16

Az algoritmus kiértékelése: > Fermat(25); "A szám összetett" Az algoritmus komplexitása: O(k log2 (n) log (log (n)) log (log (log (n))))

2.1.3.

MillerRabin

A MillerRabin algoritmus bemen˝o paramétere egy egész szám, amelyr˝ol az algoritmus eldönti, hogy prím, vagy sem. A kimenet egy sztring, melynek az értékei "A szám valószín˝ uleg prím." vagy "A szám összetett." lehetnek. Az algoritmus moduljai: a CalcLog, a ModPow és a MillerRabin modul. Az algoritmus a millerrabin.mw fájlban található. • CalcLog modul A CalcLog modult a CalcLog függvény valósítja meg. A bemen˝o paramétere egy m pozitív egész szám, kimen˝o paramétere nincs, de az algoritmus beállítja a k és q globális változókat. A k változó a log2(m/2) értéket veszi fel, a q változó pedig az m-nek a 2 maximális hatványán kívüli osztóját. A modul pszeudokódja: > CalcLog := proc(m) global k,q; k := 1; q := m; while (q mod 2 = 0) do q := q / 2: k := k + 1: end do; end proc:

Változók leírása: Változó

Típus

Feladat

m

bemen˝o param.

k

globális vált.

log2 (m/2)

q

globális vált.

m-nek a 2x kívüli osztója

oszthatósági tulajdonságait határozzuk meg

17

• ModPow modul A ModPow modult a ModPow függvény valósítja meg. A bemen˝o paraméterei m, a és x pozitív egész számok, ezeket használja fel a gyors-hatványozás módszerben, ahol az ax -t számolja. A számításokat modulo m-el végezi el. A modul pszeudokódja: > ModPow := proc(m, a, x) local r,x1,a1; x1 := x; a1 := a mod m; r := 1; while (x1 > 0) do if (type(x1,odd)) then r := (r * a1) mod m; end if; x1 := floor(x1 / 2); a1 := (a1 * a1) mod m; end do; RETURN(r); end proc:

Változók leírása: Változó

Típus

Feladat

m

bemen˝o param.

a modulus értéke

a

bemen˝o param.

az alap amit hatványozunk

a1

segéd vált.

x

bemen˝o param.

x1

lokális vált.

a ciklus feltételéhez szükséges

r

kimen˝o param.

az eredményt számoljuk benne

négyzet számításához szükséges a kitev˝o

• MillerRabin modul A MillerRabin modult a MillerRabin függvény valósítja meg. A bemen˝o paramétere egy n pozitív egész, ehhez generál egy a véletlen számot a [2,n-1] intervallumból. Az [5] jegyzetben leírt pszeudokód alapján valósítja meg a MillerRabin prímtesztet. Ha az n összetett akkor a "A szám összetett." sztringet adja kimen˝o paraméternek, különben az n valószín˝uleg prím és a "A szám valószín˝ uleg prím." sztringet adja. 18

A modul pszeudokódja: > MillerRabin := proc(n) local r,a,b,j; r := rand(2..n-1); a := r(); calcLog(n - 1); b := ModPow(n,a,q); j := k; while (j>0) do if ((j = k) and (b = 1)) or (b = n - 1) then RETURN("A szám valószín˝ uleg prím."); end if; if (j < k and b = 1) then RETURN("A szám összetett."); end if; j := j - 1; b := b^2 mod n; end do; RETURN("A szám összetett."); end proc:

Változók leírása: Változó

Típus

Feladat

n

bemen˝o param.

r

segéd vált.

a véletlen szám generálásához kell

a

lokális vált.

az véletlen alap, amivel számolunk

b

bemen˝o param.

aq mod n, az értékét ellen˝orizünk

j

lokális vált.

ciklus feltételhez kell

k

globális vált.

log2 ((n − 1)/2) értékét használjuk

q

globális vált.

(n − 1)-nek a 2x kívüli osztója

róla döntjük el hogy prím, vagy sem

19

Az algoritmus kiértékelése: > MillerRabin(113); "A szám valószín˝ uleg prím."

Az algoritmus komplexitása: O(k log3 (n))

2.2.

Fejleszt˝oi dokumentáció

A fejleszt˝oi dokumentáció a naiv prímteszt, Fermat-prímteszt és a Miller-Rabin prímteszt implementációk dokumentációiból áll. A prímtesztek a leírt sorrendben vannak dokumentálva C++, F# és Haskell programozási nyelveken. Ezzel a felbontással a dokumentációt kilenc részre osztják. Minden rész egy külön fájlban lév˝o, adott programozási nyelven implementált prímtesztet ír le. A prímtesztekre adott egy leírás, a használt könyvtárak és a program moduljai bemutatása. Mindegyik programot a függvényei alapján bontottam kisebb modulokra. A modulak felbontása: • leírás • forráskód • bemen˝o és kimen˝o paraméterek • változók leírása

20

2.2.1.

Prímtesztek implementációi

C++ 1. Naive program A program a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. BigInteger osztály megfelel˝o konstruktorával példányosít és létrehoz egy inp BigInteger típusú változót. Egy ciklust indít √ 2-t˝ol inp-ig és leellen˝orzi, hogy a ciklusváltozó osztója inp-nek vagy sem. Ha osztója, a ciklus leáll és a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben, ha a ciklusváltozó egyik esetben sem osztója, végigmegy a ciklus és a "prime" sztringet írja ki a standard kimenetre. A BigInteger osztály sqrt() függvényének a hiányában külön volt szükség egész érték˝u gyök számító függvény implementálásra. A program futtatható állománya a naiveC.exe a forráskódja pedig naiveC.cc fájlban található. • Használt könyvtárak A program használja a string.h könyvtárat, ami a parancssori paraméter beolvasásnál szükséges, az iostream.h a cout és cerr operátorok használata miatt szükséges és végül a BigIntegerLibrary.hh könyvtárra BigInteger [10] típus és a rajta definiált m˝uveletek és függvények használata miatt volt szükség. A BigInteger típus tetsz˝oleges hosszú egész számokat tud kezelni. #include <string> #include #include "BigIntegerLibrary.hh" using namespace std; • sqrt modul Leírás: Az sqrt függvény egész számokat használó algoritmussal számol gyököt, kettes számrendszer alapú algoritmussal [3]. Nagy számok kezelése miatt más lebeg˝opontos ábrázolású számokat használó algoritmussal és a meglév˝o eszközökkel nem kényelmes a megvalósítás.

21

Forráskód: BigInteger sqrt(BigInteger N){ int r = 0; for(int i= 1<<15; i!=0; i>>=1){ r = r + i; if( BigInteger(r*r) > N) r = r - i; } return(BigInteger(r)); } Bemen˝o/kimen˝o paraméterek: Bemen˝o: BigInteger típusú, aminek a gyökét akarjuk meghatározni. Kimen˝o: BigInteger típusú, a bemen˝o paraméter gyökét adja meg. Használt változók: Változó Típus

Feladat

N

BigInteger

r

int

az eredményt benne számoljuk

i

int

ciklus változó

a gyökét határozzuk meg

• main modul Leírás: A main függvény a parancssorból vár egy paramétert. Leellen˝orzi hogy egyetlen paramétert kapott vagy sem, ha nem kapott paramétert vagy több mint egyet, hibával lép ki. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. BigInteger osztály megfelel˝o konstruktorával példányosít és létrehoz egy inp BigInteger típusú változót, ami a parancssori √ sztringet kapja paraméterként. Egy ciklust indít 2-t˝ol inp-ig és minden lépésben ellen˝orzi, hogy a ciklusváltozó osztója inp-nek vagy sem. Ha osztója, egy bool változót hamisra állít és a ciklus leáll. A main függvény a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben, ha a ciklusváltozó egyik esetben sem osztója inp-nek, a ciklus végigért, a bool változó értéke true maradt és a "prime" sztringet írja ki a standard kimenetre.

22

Forráskód: int main(int argc, char *argv[]) { if (argc <= 1) { cerr << "too little parameters\n"; return 1; } else if (argc == 2){ BigInteger inp; inp = stringToBigInteger(argv[1]); bool t= true; unsigned long i; for (i=2;i<=(sqrt(inp)).toUnsignedLong();i++) { if (inp%i==0) {t=false;break;} } if (t) cout << "prime" << endl; else cout << "not prime" << endl; } else{ cerr << "too many parameters\n"; return 1; } return 0; } Bemen˝o/kimen˝o paraméterek: Bemen˝o: Sztring típusú, parancssori argumentumként. Kimen˝o: nincs. Használt változók: Változó Típus

Feladat

argc

int

argv[]

string[]

parancssori argumentumok

inp

BigInteger

a bemen˝o paramétert tárolja

t

bool

i

unsigned long

parancssori argumentumok száma

logikai segéd vált. ciklus változó

23

2. Fermat program A program a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. BigInteger osztály megfelel˝o konstruktorával példányosít és létrehoz egy inp BigInteger típusú változót. Egy elágazás eldönti, hogy a bemen˝o paraméter nagyobb vagy sem az RAND_MAX konstansnál. Ha nem nagyobb a rand() függvénnyel létrehoz egy véletlen változót 2-t˝ol inpig. Ezután egy elágazásban eldönti, hogy a véletlen változóra és az inp-re érvényes a Fermat-tétel. Ha igaz, akkor "prime" sztringet írja ki a standard kimenetre, különben a "not prime" sztringet írja ki a standard kimenetre. Ha viszont a bemen˝o paraméter nagyobb a RAND_MAX konstansnál, akkor a véletlen változót a 2-t˝ol RAND_MAX-ig intervallumból veszi és hasonlóan jár el mint az el˝oz˝o esetben. A program futtatható állománya a fermatC.exe a forráskódja pedig fermatC.cc fájlban található. • Használt könyvtárak A program használja a string.h könyvtárat, ami a parancssori paraméter beolvasásnál szükséges, az iostream.h a cout és cerr operátorok használata miatt szükséges és végül a BigIntegerLibrary.hh könyvtár a BigInteger [10] típus és rajta definiált m˝uveletek és függvények használata miatt volt szükség. A BigInteger típus tetsz˝oleges hosszú egész számokat tud kezelni. Az stdlib.h könyvtárban helyezkedik a RAND_MAX konstans, végül a time.h könyvtárra a time() függvény használatához, amely a véletlen szám seed-hez kell. #include <string> #include #include <stdlib.h> #include #include "BigIntegerLibrary.hh" using namespace std; • main modul Leírás: A main függvény a parancssorból vár egy paramétert. A C++-ban megírt Naive programhoz hasonlóan kezeli a nem megfelel˝o paraméterszámot. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. BigInteger osztály megfelel˝o konstruktorával példányosít és létrehoz egy 24

inp BigInteger típusú változót. Egy t logikai változót beállít hamis értékre. Egy elágazás eldönti, hogy a bemen˝o paraméter nagyobb vagy sem a RAND_MAX konstansnál. Mivel a rand() függvény egy tetsz˝oleges int típusú számot generál, ha intervallum között szeretnénk egy véletlen számot, akkor a rand() függvény kimenetének a modulusát vesszük. Ezt abban az esetben csinálja a program ha inp − 1 > RAND_MAX-nál. Abban az esetben ha a paraméter kisebb a RAND_MAX-tól, nem szükséges modulust számolni, ekkor a rand() függvénnyel létrehoz egy véletlen változót 2-t˝ol inp-ig. Ezután egy elágazásban eldönti, hogy a véletlen változóra és az inp-re érvényes a Fermat-tételvagy sem. Ha érvényes, a t változó értékét igazra állítja és a "prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben a t változó értékét hamisra állítja és a "not prime" sztringet írja ki. Ha inp−1 > RAND_MAX-nál a rand() függvény értékét mod inp-el vesszük, ezután a Fermat-tétel érvényességének az ellen˝orzése után, ugyanazt a a kódot hajtja végre, mint az el˝oz˝o esetben. A véletlen számok generálásánál nem vesszük figyelembe a 2-nél kisebbeket. A ModPow algoritmus megvalósítására nem volt szükség, mert a BigInteger osztály tartalmazza a modexp(BigInteger, BigUnsigned, Bigunsigned) függvényt, ami gyors-hatványozást valósít meg modulussal számolva. Forráskód: ... srand ( time(NULL) ); BigUnsigned inp; inp = stringToBigUnsigned(argv[1]); bool t = false; if (inp.toInt() >= RAND_MAX){ int ran1 = rand(); while (ran1 <2) {ran1 = rand();} BigInteger a = BigInteger(rand()); if (modexp(a,inp-1,inp)== 1) t= true; }

25

else{ BigInteger ran2 = BigInteger(rand())%inp; while (ran2 <2) { ran2 = BigInteger(rand())%inp; } BigInteger a = BigInteger(rand())%inp; if (modexp(a,inp-1,inp)== 1) t= true; } if (t) cout << "prime" << endl; else cout << "not prime" << endl; ... Bemen˝o/kimen˝o paraméterek: Bemen˝o: Sztring típusú, parancssori argumentumként. Kimen˝o: nincs. Használt változók: Változó Típus

Feladat

argc

int

argv[]

string[]

parancssori argumentumok

inp

BigInteger

a bemen˝o paramétert tárolja

ran1

int

véletlen változó

ran2

BigInteger

véletlen változó

t

bool

i

unsigned long

parancssori argumentumok száma

logikai segéd vált. ciklus változó

3. MillerRabin program A program a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. BigInteger osztány megfelel˝o konstruktorával példányosít és létrehoz egy inp BigInteger típusú változót. Egy elágazás eldönti, hogy a bemen˝o paraméter nagyobb vagy sem az RAND_MAX konstansnál. Ha nem nagyobb a rand() függvénnyel létrehoz egy véletlen változót 2-t˝ol inpig. Ezután egy elágazásban eldönti, hogy a véletlen változóra és az inp-re érvényes a Fermat-tétel. Ha igaz, akkor "prime" sztringet írja ki a standard kimenetre, különben a "not prime" sztringet írja ki a standard kimenetre. Ha viszont a bemen˝o paraméter nagyobb a RAND_MAX konstansnál, akkor a véletlen változót a 2-t˝ol RAND_MAX-ig intervallumból veszi és hasonlóan jár el mint az el˝oz˝o eset26

ben. A program futtatható állománya a millerrabinC.exe a forráskódja pedig millerrabinC.cc fájlban található. • Használt könyvtárak A program használja a string.h könyvtárat, ami a parancssori paraméter beolvasásnál szükséges, az iostream.h a cout és cerr operátorok használata miatt szükséges és végül a BigIntegerLibrary.hh könyvtár a BigInteger [10] típus és rajta definiált m˝uveletek és függvények használata miatt volt szükség. A BigInteger típus tetsz˝oleges hosszú egész számokat tud kezelni. Az stdlib.h könyvtárban helyezkedik a RAND_MAX konstans, végül a time.h könyvtárra a time() függvény használatához, amely a random seed-hez kell. #include <string> #include #include <stdlib.h> #include #include "BigIntegerLibrary.hh" using namespace std; • calcLog modul Leírás: A modul a bemen˝o n paramétert felbontja 2k q-ra, a k és a q globális változók, melyeket beállít. Forráskód: unsigned long k,q; void calcLog(unsigned long m){ k = 1 q = m; while (q%2==0){ q = q / 2; k++; } } 27

Bemen˝o/kimen˝o paraméterek: Bemen˝o: unsigned long, a 2k q alakra felbontandó szám. Kimen˝o: nincs. Használt változók: Változó Típus

Feladat

m

unsigned long

ezt a számot bontjuk fel

k

unsigned long

globális vált. k, a 2k q-ból

q

unsigned long

globális vált. q, a 2k q-ból

• main modul Leírás: A main függvény a parancssorból vár egy paramétert. A C++-ban megírt Naive programhoz hasonlóan kezeli a nem megfelel˝o paraméterszámot. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. BigInteger osztány megfelel˝o konstruktorával példányosít és létrehoz egy inp BigInteger típusú változót. Egy t logikai változót beállít hamis értékre. A véletlen szám generálást úgy oldja meg ahogy a fejezetben leírt Fermat program. A bemen˝o paramétert˝ol függ˝oen két eset lesz és mindkét esetben a ModPow függvény segítségével hajtja végre a 2.1.3. fejezetben leírt algoritmust. A ModPow algoritmus megvalósítására nem volt szükség, mert a BigInteger osztály tartalmazza a modexp(BigInteger, BigUnsigned, Bigunsigned) függvényt, ami gyors-hatványozást valósít meg modulussal számolva. Forráskód: ... srand ( time(NULL) ); BigUnsigned inpu; BigInteger inp; inpu = stringToBigUnsigned(argv[1]); inp = stringToBigInteger(argv[1]); bool t = false; calcLog(inp.toUnsignedLong() - 1); unsigned long j = k;

28

if (inp.toInt() > RAND_MAX){ int ran1 = rand(); while (ran1 < 2){ran1 = rand();} BigInteger a = BigInteger(ran1); BigUnsigned b = modexp(a,BigUnsigned(q),inpu); while (j>0){ if (((j == k) && (b == BigUnsigned(1))) || (b == inpu-BigUnsigned(1))){ t = true; cout<<"prime"<< endl; break; } else if ((j0){ if (((j == k) && (b == 1)) || (b == inpu-1)){t = true; break;} else if ((j
Bemen˝o/kimen˝o paraméterek: Bemen˝o: sztring típusú, parancssori argumentumként. Kimen˝o: nincs. Használt változók: Változó Típus

Feladat

argc

int

argv[]

string[]

parancssori argumentumok

inp

BigInteger

a bemen˝o paramétert tárolja

inpu

BigInteger

a bemen˝o paramétert tárolja

ran1

int

véletlen változó

ran2

BigInteger

véletlen változó

k

unsigned long

globális vált. k, a 2k q-ból

q

unsigned long

globális vált. q, a 2k q-ból

t

bool

i

unsigned long

parancssori argumentumok száma

logikai segéd vált. ciklus változó

F# 1. Naive program A program a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. Ez után létrehoz egy n BigInteger típusú √ változót. Egy ciklust indít 2-t˝ol n-ig és leellen˝orzi, hogy a ciklusváltozó osztója n-nek vagy sem. Ha osztója, a ciklus leáll és a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben, ha a ciklusváltozó egyik esetben sem osztója, végigmegy a ciklus és a "prime" sztringet írja ki a standard kimenetre. A program a TestPrime, Naive és a Program modulból áll. A program futtatható állománya a naiveF.exe a forráskódja pedig naiveF.fs fájlban található. • Használt könyvtárak A Naive program a Microsoft.FSharp.Core.Operators névtérb˝ol típus konvertálási függvényeket használ, a System.Numerics névtérben a BigInteger osztály található, amely megvalósítja a tetsz˝oleges méret˝u egészeket. Továbbá, a Microsoft.FSharp.Collections névtérre is szükségünk volt a Seq típus használata miatt. A System könyvtárban általános eszközök találhatók.

30

#light open Microsoft.FSharp.Core.Operators open System.Numerics open Microsoft.FSharp.Collections open System • TestPrime modul Leírás: A TestPrime modul végezi el a feladat nagy részét: egy n bemen˝o egészre, a szám gyökéig lépeget˝o ciklusban eldönti, hogy van valódi osztója, vagy sem. √ A program a Seq típusba sorolja fel 2-t˝ol n − ig és mindegyikre meghív egy függvényt, amely az oszthatóságot ellen˝orizi. Forráskód: let TestPrime (n:BigInteger) = { 2L..Convert.ToInt64((sqrt (double n))) } |> Seq.forall (fun x -> n%(BigInteger x) <> BigInteger.Zero) Bemen˝o/kimen˝o paraméterek: Bemen˝o: BigInteger, a tesztelend˝o szám. Kimen˝o: bool, a bemen˝o szám prímségét határozza meg. Használt változók: Változó Típus

Feladat

n

unsigned long

ennek a számnak adjuk meg a prímségét.

x

unsigned long

segéd vált., ciklus

• Naive modul Leírás: A modul a TestPrime függvény kimenete alapján "prime" illetve "not prime" sztringet ír a standarad kimenetere. Forráskód:

31

let Naive (n:BigInteger) = if (not (TestPrime n)) then printf "not prime\n" else printf "prime\n" Bemen˝o/kimen˝o paraméterek: Bemen˝o: BigInteger, a tesztelend˝o szám. Kimen˝o: nincs. Használt változók: Változó Típus n

Feladat

BigInteger

a prímsége alapján cselekszik a program

• Program modul Leírás: A Program modul a GetCommandLineArgs() függvény segítségével éri el a parancssori argumentumokat, majd ezeket listává konvertálja. A lista els˝o elemét BigInteger típusá konvertálja, majd átadja a Naive függvénynek. Ha nincs parancssori paraméter, a Program függvény hibával tér vissza, ha viszont túl sok paraméter van, akkor veszi az els˝o paramétert és nem veszi figyelembe a többit. Forráskód: let Program ()

=

let args = Environment.GetCommandLineArgs() |> Array.toList let intArg = try BigInteger.Parse(args.[1]) with | _ -> failwith "No integer argument given" Naive (intArg) A Program függvény meghívása: Program () 32

Bemen˝o/kimen˝o paraméterek: Bemen˝o: Nincs. Kimen˝o: A Naive függvény kimenete. Használt változók: Változó Típus args

unit

intArg

BigInteger

Feladat a Naive függvény kimenetét tárolja az argumentumlista els˝o eleme

2. Fermat program A Fermat program a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. Ez után létrehoz egy n BigInteger típusú változót. A Fermat algoritmus alapján leellen˝orzi, hogy an−1 ≡ 1 mod n egy a véletlen számra. Ha nem igaz, akkor a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben a "prime" sztringet írja ki. A program a PowMod, Test, RandomWrap és a Program modulból áll. A program futtatható állománya a fermatF.exe a forráskódja pedig fermatF.fs fájlban található. • Használt könyvtárak A Fermat program a Microsoft.FSharp.Math névtérb˝ol matematikai függvényeket használ, a System.Numerics névtérben a BigInteger osztály található, amely megvalósítja a tetsz˝oleges méret˝u egészeket. Továbbá, a Microsoft.FSharp.Collections névtérre is szükségünk volt a Seq típus használata miatt. A System könyvtárban általános eszközök találhatók. A véletlenszer˝u számok generálásahoz szükséges függvények a System.Diagnostics névtér alatt találhatók. #light open System open System.Diagnostics open Microsoft.FSharp.Collections open Microsoft.FSharp.Math open System.Numerics

33

• PowMod Leírás: A modul gyorshatványozás módszerrel hatvány modulust számol. Rekurzív hívásokkal valósítja meg a ciklust. Forráskód: let rec PowMod a n m = if (n = BigInteger.Zero) then BigInteger.One else if (n % (BigInteger 2) = BigInteger.Zero) then (BigInteger.Pow (PowMod a (n/(BigInteger 2)) m,2)) % m else (a * (PowMod a (n-BigInteger.One) m)) % m Bemen˝o/kimen˝o paraméterek: Bemen˝o: BigInteger - BigInteger - BigInteger, az alap, a kitev˝o és a modulus. Kimen˝o: BigInteger, an mod m. Használt változók: Változó Típus

Feladat

a

BigInteger

a hatványozás alapja

n

BigInteger

a hatványozás kitev˝oje

m

BigInteger

a modulus

• Test modul Leírás: A modul egy elágazással ellen˝orzi, hogy an−1 ≡ 1 mod n fennál, vagy sem. Forráskód: let Test (a:BigInteger) (n:BigInteger) = let exp = n-BigInteger.One (PowMod a exp n) = BigInteger.One Bemen˝o/kimen˝o paraméterek: Bemen˝o: BigInteger - BigInteger, a tesztelend˝o szám és az alap. Kimen˝o: bool, an−1 ≡ 1 mod n érvényes, vagy sem. 34

Használt változók: Változó Típus

Feladat

a

BigInteger

bemen˝o vált.

exp

BigInteger

segéd vált., a kitev˝ot határozza meg

n

BigInteger

bemen˝o vált.

• RandomWrap modul Leírás: A modul 2-t˝ol n − 1-ig intervallumban állt el˝o véletlen számokat. A véletlen szám generátor korlátjait hasonlóan oldja meg mint a C++ Fermat és MillerRabin prímtesztek programjai. Meghívja a Test függvényta bemen˝o és a véletlen számra. Ha nem igaz, akkor a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben a "prime" sztringet írja ki. Forráskód: let RandomWrap (n:uint64) = let Rand = new System.Random() if n < Convert.ToUInt64(Int32.MaxValue) then let a = Rand.Next(1, Convert.ToInt32(n)-1) let n1 = Convert.ToInt64(n) if (Test (BigInteger a) (BigInteger n1)) then printf "prime\n" else printf "not prime\n" else let a = Rand.Next(1, Int32.MaxValue) let n1 = Convert.ToInt64(n) if (test (BigInteger a) (BigInteger n1)) then printf "prime\n" else printf "not prime\n" () • Program modul Leírás: A Program modul a GetCommandLineArgs() függvény segítségével éri el a parancssori argumentumokat, majd ezeket listává konvertálja. A lista els˝o 35

elemét BigInteger típusá konvertálja, majd átadja a RandomWrap függvénynek. Ha nincs parancssori paraméter, a Program függvény hibával tér vissza, ha viszont túl sok paraméter van, akkor veszi az els˝o paramétert és nem veszi figyelembe a többit. Forráskód: let Program ()

=

let args = Environment.GetCommandLineArgs() |> Array.toList let intArg = try BigInteger.Parse(args.[1]) with | _ -> failwith "No integer argument given" RandomWrap (intArg) A Program függvény meghívása: Program () Bemen˝o/kimen˝o paraméterek: Bemen˝o: Nincs. Kimen˝o: A RandomWrap függvény kimenete. Használt változók: Változó Típus args

unit

intArg

BigInteger

Feladat a RandomWrap függvény kimenetét tárolja az argumentumlista els˝o eleme

3. MillerRabin program A MillerRabin program a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring típusban lesz. Ez után a MillerRabin algoritmust hajtja végre egy véletlen számra és a bemen˝o paraméterre. Ha a MillerRabin megvalósítása hamis értéket ad, akkor a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben a "prime" sztringet írja ki. A program a BoolList, MillerRabin, RandomWrap és a Program modulból áll. A program futtatható állo36

mánya a millerrabinF.exe a forráskódja pedig millerrabinF.fs fájlban található. • Használt könyvtárak A Fermat program a Microsoft.FSharp.Math névtérb˝ol matematikai függvényeket használ, a System.Numerics névtérben a BigInteger osztály található, amely megvalósítja a tetsz˝oleges méret˝u egészeket. Továbbá, a Microsoft.FSharp.Collections névtérre is szükségünk volt a Seq típus használata miatt. A System könyvtárban általános eszközök találhatók. A véletlenszer˝u számok generálásahoz szükséges függvények a System.Diagnostics névtér alatt találhatók. #light open System open System.Diagnostics open Microsoft.FSharp.Collections open Microsoft.FSharp.Math open System.Numerics • BoolList Leírás: A modul a bemen˝o n paramétert felírja a bináris alakjának a fordítottjára. Forráskód: let BoolList (n:BigInteger) = let mutable m = n let mutable r = [] while m > BigInteger.Zero do r <- r @ [(m % (BigInteger 2))] m <- m / BigInteger 2 r Bemen˝o/kimen˝o paraméterek: Bemen˝o: Biginteger, a tesztelend˝o szám. Kimen˝o: bool[], a bemen˝o paraméter bináris fordítottja. Használt változók: 37

Változó

Típus

Feladat

n

BigInteger

ezt a számot írjuk fordított bináris alakra

r

BigInteger

lokális vált., a maradék

m

BigInteger

lokális vált., az osztás maradéka

• MillerRabin modul Leírás: A modul a bemen˝o n és a paraméterekre végrehajtja a MillerRabin algoritmust. A gyorshatványozás módszert modulussal az algoritmus végrehajtása közben számolja [2]. Forráskód: let MillerRabin (a:BigInteger) (n:BigInteger) = let (b:List) = BoolList (n - BigInteger.One) let mutable d = BigInteger.One let mutable t = false let revList = [0 .. b.Length-1 ] |> List.rev for i in revList do let x = d d <- (d*d) % n if (d = BigInteger.One && x <> BigInteger.One && x <> n-BigInteger.One) then t <- true if b.[i] = BigInteger.One then d <- (d*a) % n if d <> BigInteger.One then t <- true t Bemen˝o/kimen˝o paraméterek: Bemen˝o: BigInteger - BigInteger, a tesztelend˝o szám és a véletlen alap. Kimen˝o: BigInteger, igaz a MillerRabin algoritmus, vagy sem.

38

Használt változók: Változó Típus

Feladat

a

BigInteger

bemen˝o param.

n

BigInteger

bemen˝o param.

b

bool[]

a tesztelend˝o adat bináris felírása

d

BigInteger

segéd vált. a gyorshatványozáshoz

t

bool

x

BigInteger

i

int

lokális vált. a MillerRabin eredményét adja meg segéd vált. a gyorshatványozáshoz ciklus vált.

• RandomWrap modul Leírás: A modul 2-t˝ol n − 1-ig intervallumban állt el˝o véletlen számokat. A véletlen szám generátor korlátjait hasonlóan oldja meg mint a C++ Fermat és MillerRabin prímtesztek programjai. Meghívja a MillerRabin függvényt a bemen˝o és a véletlen számra. Ha nem igaz, akkor a "not prime" sztringet írja ki a standard kimenetre. Ellenkez˝o esetben a "prime" sztringet írja ki. Forráskód: let RandomWrap (n:uint64) = let Rand = new System.Random() if n < Convert.ToUInt64(Int32.MaxValue) then let a = Rand.Next(1, Convert.ToInt32(n)-1) let n1 = Convert.ToInt64(n) if (MillerRabin (BigInteger a) (BigInteger n1)) then printf "prime\n" else printf "not prime\n" else let a = Rand.Next(1, Int32.MaxValue) let n1 = Convert.ToInt64(n) if (MillerRabin (BigInteger a) (BigInteger n1)) then printf "prime\n" else printf "not prime\n" ()

39

• Program modul Leírás: A Program modul a GetCommandLineArgs() függvény segítségével éri el a parancssori argumentumokat, majd ezeket listává konvertálja. A lista els˝o elemét BigInteger típusá konvertálja, majd átadja a RandomWrap függvénynek. Ha nincs parancssori paraméter, a Program függvény hibával tér vissza, ha viszont túl sok paraméter van, akkor veszi az els˝o paramétert és nem veszi figyelembe a többit. Forráskód: let Program ()

=

let args = Environment.GetCommandLineArgs() |> Array.toList let intArg = try BigInteger.Parse(args.[1]) with | _ -> failwith "No integer argument given" RandomWrap (intArg) A Program függvény meghívása: Program () Bemen˝o/kimen˝o paraméterek: Bemen˝o: Nincs. Kimen˝o: A RandomWrap függvény kimenete. Használt változók: Változó Típus args

unit

intArg

BigInteger

Feladat a RandomWrap függvény kimenetét tárolja az argumentumlista els˝o eleme

40

Haskell 1. Naive program A program main modulja a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring listában lesz. A main modul átadja a sztring listát a mainWithArgs modulnak, mely mintaillesztéssel kiveszi a lista egyetlen elemét és meghívja rá a naive modulbeli naive függvényt. Ha a naive függvény igaz értéket ad vissza, akkor a mainWithArgs a "prime" sztringet írja ki a standard kimenetre, különben, hamis értékre a a "not prime" sztringet írja ki. A na√ ive modul egy ciklusban ellen˝orzi, hogy a bemen˝o n-re létezik 2-t˝ol n-ig osztója vagy sem. Az iSqrt modul számolja a gyököt. Minden modult egy-egy függvény valósít meg. A program futtatható állománya a naiveH.exe a forráskódja pedig naiveH.hs fájlban található. • Használt könyvtárak Haskell module Main-be ágyazva program a Prelude könyvtárat használja, amit nem kellett külön importálni. Ezen kívül a parancssori paraméterek kezeléséhez szükség volt a System.Environment könyvtárra. module Main where import System.Environment • iSqrt modul Leírás: Az iSqrt modul gyököt számol. A bemen˝o Integer típusú változót Float típusra konvertálja, kiszámolja a gyökét az sqrt függvénnyel, majd veszi az alsó egész részét és ezt adja kimen˝o paraméternek. Forráskód: iSqrt ::

Integer -> Integer

iSqrt n = floor (sqrt (fromIntegral n)) Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer típusú, a gyökét keressük. Kimen˝o: Integer típusú, a bemen˝o paraméter gyöke. Használt változók: Változó Típus n

Integer

Feladat a szám aminek a gyökét számoljuk 41

• naive modul Leírás: A naive modul végzi az algoritmus jelent˝os részét. Rekurzívan végigfut a n − 1-t˝ol 2-ig, ahol n a bemen˝o paraméter, és ellen˝orzi, hogy az n osztható az intervallumbeli számokkal vagy sem. Ha osztható, a ciklus megáll és hamis értéket ad vissza kimen˝o paraméterként. Különben, ha végig futott a ciklus, igaz értéket ad. Forráskód: naive :: Integer -> Bool naive n = s $ n-1 where s m | (m == 1) = True | ((n ‘mod‘ m) == 0) = False |

otherwise = (s (m-1))

Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer típusú, róla döntjük el hogy prím, vagy sem. Kimen˝o: bool típusú, a bemen˝o param. osztójai létezését˝ol függ˝oen. Használt változók: Változó Típus

Feladat

n

Integer

összetett vagy prím szám

s

function

rekurzív segéd függvény

m

BigInteger

az s bemen˝o paramétere

• main modul Leírás: A parancssori argumentumok listáját beolvassa egy változóba és átadja a mainWithArgs modulnak. Forráskód: main :: IO () main = do s <- getArgs mainWithArgs s

42

Bemen˝o/kimen˝o paraméterek: Bemen˝o: Nincs. Kimen˝o: Nincs. Használt változók: Változó Típus s

Feladat

string[]

parancssori paramétereket tartalmazza

• mainWithArgs modul Leírás: Egy bemen˝o sztring lista egyetlen elemét mintaillesztéssel veszi ki. Abban az esetben, ha több eleme van, hibaüzenetet ad. Az n lista elemre meghívja a naive függvényt. read függvény használatával kikövetkezteti, hogy milyen típusú paraméter kell a naive függvénynek és arra konvertálja az nt. Attól függ˝oen, hogy a naive függvény igaz vagy hamis értéket adott, a putStrLn mellékhatásos függvénnyel a standard kimenetre ír. Forráskód: mainWithArgs [n] = do putStrLn $ if naive (read n) then "prime" else "not prime" mainWithArgs _ = error "usage: main " Bemen˝o/kimen˝o paraméterek: Bemen˝o: Sztring lista típusú, parancssori argumentum. Kimen˝o: Nincs. Használt változók: Változó Típus n

string

Feladat parancssori argumentum

2. Fermat algoritmus A program main modulja a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring listában lesz. A main modul átadja a sztring listát a mainWithArgs modulnak, mely mintaillesztéssel kiveszi a lista egyetlen elemét, deklarál egy véletlen szám seed-et és meghívja rá és a bemen˝o paraméterre a fermat modulbeli fermat függvényt. Ha a fermat függvény igaz értéket ad vissza, akkor a mainWithArgs a "prime" sztringet írja ki a standard kimenetre, 43

különben, hamis értékre a a "not prime" sztringet írja ki. A fermat függvény eldönti a bemen˝o számról, hogy megfelel a Fermat-tételnek vagy sem. Ha megfelel, akkor igaz értéket ad, különben hamisat. A program futtatható állománya a fermatH.exe a forráskódja pedig fermatH.hs fájlban található. • Használt könyvtárak A program a Prelude könyvtárat használja, amit nem kellett külön importálni. Ezen kívül a parancssori paraméterek kezeléséhez szükség volt a System.Environment könyvtárra és a System.Random könyvtárra a véletlen számok generálásához. module Main where import System.Environment import System.Random • sqr modul Leírás: Az sqr modul a második paraméter négyzetét számolja modulo az els˝o paraméter. Forráskód: sqr m x = (x * x) ‘mod‘ m Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer - Integer, az es˝o a modulo- a második a négyzet. Kimen˝o: Integer, x2 mod m. Használt változók: Változó Típus

Feladat

m

Integer

a modulo

x

Integer

a négyzetre emelend˝o szám

• powMod modul Leírás: Az powMod modul három bemen˝o paramétert vár: b-t, n-t és m-t. Gyorshatványozás módszerrel, közben modulussal számolva a bn mod m-et számol.

44

Forráskód: powMod b 0 m = 1 powMod b n m | even n = sqr m (powMod b (n ‘div‘ 2) m) | odd n = (b * powMod b (n - 1) m) ‘mod‘ m Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer típusúak, b, n és m . Kimen˝o: Integer, bn mod m Használt változók: Változó Típus

Feladat

b

Integer

a bázis amit hatványozunk

n

Integer

a hatvány

m

Integer

a modulus

• fermat modul Leírás: A modul egy elágazásból áll, mely leellen˝orzi, hogy az n bemen˝o paraméterre és a g bemen˝o paraméter segítségével generált véletlen számra érvényes a Fermat-tétel vagy sem. Ha érvényes, akkor a fermat függvény igaz értéket ad, különben hamisat. Forráskód: fermat :: StdGen -> Integer -> Bool fermat g n = powMod a (n-1) n /= 1 where (a,_) = randomR (2, n-1) g Bemen˝o/kimen˝o paraméterek: Bemen˝o: StdGen - Integer, véletlen szám seed - az ellen˝orizend˝o szám . Kimen˝o: bool, eldönti az n prímségét. Használt változók: Változó Típus

Feladat

g

StdGen

a véletlen szám generátor

n

Integer

prím vagy összetett egész

a

Integer

egy véletlen szám 2-t˝ol n − 1-ig

45

• main modul Leírás: A parancssori argumentumok listáját beolvassa egy változóba és átadja a mainWithArgs modulnak. Forráskód: main :: IO () main = do s <- getArgs mainWithArgs s Bemen˝o/kimen˝o paraméterek: Bemen˝o: Nincs. Kimen˝o: Nincs. Használt változók: Változó Típus s

string[]

Feladat parancssori paramétereket tartalmazza

• mainWithArgs modul Leírás: Egy bemen˝o sztring lista egyetlen elemét mintaillesztéssel veszi ki. Abban az esetben, ha több eleme van, hibaüzenetet ad. Az n lista elemre és egy véletlen szám seed-re meghívja a fermat függvényt. read függvény használatával kikövetkezteti, hogy milyen típusú paraméter kell a fermat függvénynek és arra konvertálja az n-t. Attól függ˝oen, hogy a fermat függvény igaz vagy hamis értéket adott, a putStrLn mellékhatásos függvénnyel a standard kimenetre ír. Forráskód: mainWithArgs [n] = do g <- newStdGen putStrLn $ if fermat g (read n) then "prime" else "not prime" mainWithArgs _ = error "usage: main "

46

Bemen˝o/kimen˝o paraméterek: Bemen˝o: Sztring lista típusú, parancssori argumentum. Kimen˝o: Nincs. Használt változók: Változó Típus n

string

Feladat parancssori argumentum

3. MillerRabin program A program main modulja a parancssorból vár egy paramétert. A parancssorból történ˝o beolvasás után a paraméter sztring listában lesz. A main modul átadja a sztring listát a mainWithArgs modulnak, mely mintaillesztéssel kiveszi a lista egyetlen elemét, deklarál egy véletlen szám seed-et és meghívja rá és a bemen˝o paraméterre a fermat modulbeli millerRabin függvényt. Ha a MillerRabin függvény igaz értéket ad vissza, akkor a mainWithArgs a "prime" sztringet írja ki a standard kimenetre, különben, hamis értékre a a "not prime" sztringet írja ki. A millerRabin függvény a MillerRabin algoritmus alapján dönti el a bemen˝o számról, összetett vagy valószín˝uleg prím. Ha valószín˝uleg prím, akkor igaz értéket ad, különben hamisat. A program futtatható állománya a millerrabinH.exe a forráskódja pedig millerrabinH.hs fájlban található. • Használt könyvtárak A program a Prelude könyvtárat használja, amit nem kellett külön importálni. Ezen kívül a parancssori paraméterek kezeléséhez szükség volt a System.Environment könyvtárra és a System.Random könyvtárra a véletlen számok generálásához. module Main where import System.Environment import System.Random • sqr modul Leírás: Az sqr modul a második paraméter négyzetét számolja modulo az els˝o paraméter. Forráskód: sqr m x = (x * x) ‘mod‘ m 47

Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer - Integer, az es˝o a modulo- a második a négyzet. Kimen˝o: Integer, x2 mod m. Használt változók: Változó Típus

Feladat

m

Integer

a modulo

x

Integer

a négyzetre emelend˝o szám

• powMod modul Leírás: Az powMod modul három bemen˝o paramétert vár: b-t, n-t és m-t. Gyorshatványozás módszerrel, közben modulussal számolva a bn mod m-et számol. Forráskód: powMod b 0 m = 1 powMod b n m | even n = sqr m (powMod b (n ‘div‘ 2) m) | odd n = (b * powMod b (n - 1) m) ‘mod‘ m Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer típusúak, b, n és m . Kimen˝o: Integer, bn mod m Használt változók: Változó Típus

Feladat

b

Integer

a bázis amit hatványozunk

n

Integer

a hatvány

m

Integer

a modulus

• decomposite modul Leírás: A modul a bemen˝o n paramétert felbontja 2k q-ra.

48

Forráskód: decomposite n = dec (0,n) where dec (k,q) | ((q ‘mod‘ 2) == 0) = dec (k+1,q ‘div‘ 2) | otherwise = (k,q) Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer - Integer, az es˝o a modulo- a második a négyzet. Kimen˝o: (Integer,Integer), (k, q) pár a 2k q-ból. Használt változók: Változó Típus

Feladat

n

Integer

ezt a számot bontjuk fel

k

Integer

k, a 2k q-ból

q

Integer

q, a 2k q-ból

• millerRabin modul Leírás: A millerRabin függvény a 2.1.3.-ban leírt algoritmus alapján dönti el a bemen˝o számról, összetett vagy valószín˝uleg prím. Ha valószín˝uleg prím, akkor igaz értéket ad, különben hamisat. A powMod függvényt használja a hatvány modulusának számítására, a decomposite függvényt pedig az n bemen˝o paraméter felbontására. Forráskód: millerRabin :: StdGen -> Integer -> Bool millerRabin g n = loops (decF, b1) where b1 = powMod r decS n (decF, decS) = decomposite (n-1) (r,_) = randomR (2, n-1) g loops (j,b) | (j < decF && b == 1) = True | ((j == decF && b == 1)||(b == n-1)) = False | (j > 0) = loops (j-1, b^2 ‘mod‘ n) | otherwise = True 49

Bemen˝o/kimen˝o paraméterek: Bemen˝o: Integer, a bemen˝o paraméter, aminek a prímségét döntjük el. Kimen˝o: bool, a bemen˝o paraméter valószín˝uleg prím, vagy sem. Használt változók: Változó Típus

Feladat

g

StdGen

n

Integer

a prímségét döntjük el

decF

Integer

n = 2decF decS-felbontásban szerepel

decS

Integer

n = 2decF decS-felbontásban szerepel

b1

Integer

a rdecS mod n érték

j

Integer

a loop rekurzív segéd függvény változója

b

Integer

a loop rekurzív segéd függvény változója

véletlen szám seed

• main modul Leírás: A parancssori argumentumok listáját beolvassa egy változóba és átadja a mainWithArgs modulnak. Forráskód: main :: IO () main = do s <- getArgs mainWithArgs s Bemen˝o/kimen˝o paraméterek: Bemen˝o: Nincs. Kimen˝o: Nincs. Használt változók: Változó Típus s

string[]

Feladat parancssori paramétereket tartalmazza

• mainWithArgs modul Leírás: Egy bemen˝o sztring lista egyetlen elemét mintaillesztéssel veszi ki. Abban az esetben, ha több eleme van, hibaüzenetet ad. Az n lista elemre és egy véletlen szám seed-re meghívja a fermat függvényt. read függvény használatával kikövetkezteti, hogy milyen típusú paraméter kell a fermat függvénynek és arra konvertálja az n-t. Attól függ˝oen, hogy a fermat függvény igaz 50

vagy hamis értéket adott, a putStrLn mellékhatásos függvénnyel a standard kimenetre ír. Forráskód: mainWithArgs [n] = do g <- newStdGen putStrLn $ if fermat g (read n) then "prime" else "not prime" mainWithArgs _ = error "usage: main " Bemen˝o/kimen˝o paraméterek: Bemen˝o: Sztring lista típusú, parancssori argumentum. Kimen˝o: Nincs. Használt változók: Változó Típus n

2.3.

string

Feladat parancssori argumentum

Felhasználói útmutató

A dolgozatban implementált programok használata fordításból és futtatásból áll. Gyakran használt Unix alapú és Windows operációs rendszerekben mutatom meg a programok felhasználási módját. 1. Unix alapú operációs rendszerek (Linux, OS X...) Ahhoz, hogy a programokat le lehessen fordítani és futtatni Unix alapú rendszereken, adott programozási nyelvekhez fordítóprogramra lesz szükség. C++ fordító: http://gcc.gnu.org/ F# fordító: http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/ Haskell fordító: http://www.haskell.org/ F# kellék: http://www.mono-project.com/Main_Page A C++ programok fordításához le kell tölteni a BigInteger könyvtárat [10]. A könyvtár elemei össze vannak kötve és habár csak a BigIntegerLibrary van hozzáadva a forráskódhoz, a BigInteger összes elemére szükség van. Miután a forráskódot tartalmazó fájlt belemásoljuk a biginteger könyvtárba, egy make parancs elintítására van szükség: 51

$ make g++ -c -O2 -Wall -Wextra -pedantic fermatC.cc g++ fermatC.o BigUnsigned.o BigInteger.o BigIntegerAlgorithms.o BigUnsignedInABase.o BigIntegerUtils.o -o fermatC

A program egy parancssori argumentumot vár. Ha több vagy kevesebb argumentum van, hibát ad, különben végrehajtja rá a prímtesztet és "prime" vagy "not prime" sztringet írja ki a standard kimenetre. $ ./fermatC too little parameters $ ./fermatC 43 45 too many parameters $ ./fermatC 23413 not prime $ ./fermatC 234135 not prime

Az F# programok fordításához fel kell instalállni a Mono rendszert és ezen keresztül lehet meghívni a F# fordítót a forrás fájlra a fsc paranccsal. $ mono bin/fsc.exe millerrabinF.fs Microsoft (R) F# 2.0 Compiler build 2.0.0.0 Copyright (c) Microsoft Corporation. All Rights Reserved.

A program egy parancssori argumentumot vár. Ha több argumentum van csak az els˝ot veszi, ha hiányzik az argumentum kezeletlen kivétellet dob, különben végrehajtja rá a prímtesztet és "prime" vagy "not prime" sztringet írja ki a standard kimenetre.

52

$ mono millerrabinF.exe Unhandled Exception: System.Exception: No integer argument given at MillerrabinF.Program () [0x00000] in :0 at <StartupCode$millerrabinF>.$MillerrabinF.main@ () [0x00000] in :0 $ mono millerrabinF.exe 23 67 prime $ mono millerrabinF.exe 23413 not prime $ mono millerrabinF.exe 234135 not prime

A Haskell program futtatásához meg kell hívni a ghc parancsot a forrás fájlra. $ ghc fermatH.hs

A program egy parancssori argumentumot vár. Ha több vagy kevesebb argumentum van, hibát ad, különben végrehajtja rá a prímtesztet és "prime" vagy "not prime" sztringet írja ki a standard kimenetre. $ ./a.out a.out: hasznalat: main $ ./a.out 34 67 a.out: hasznalat: main $ ./a.out 23413 not prime $ ./a.out 234135 not prime

53

2. Windows operációs rendszerek (XP, Vista...) Ahhoz, hogy a programokat le lehessen fordítani és futtatni Windows rendszereken, adott programozási nyelvekhez fordítóprogramra lesz szükség. C++ fordító: http://gcc.gnu.org/ F# fordító: http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/ Haskell fordító: http://www.haskell.org/ A C++ programok fordításához le kell tölteni a BigInteger könyvtárat [10]. A könyvtár elemei össze vannak kötve és habár csak a BigIntegerLibrary van hozzáadva a forráskódhoz, a BigInteger összes elemére szükség van. Miután a forráskódot tartalmazó fájlt belemásoljuk a biginteger könyvtárba, egy make parancs elintítására van szükség: >make g++ millerrabinC.o BigUnsigned.o BigInteger.o BigIntegerAlgorithms.o BigUnsignedInABas e.o BigIntegerUtils.o -o millerrabinC

A program egy parancssori argumentumot vár. Ha több vagy kevesebb argumentum van, hibát ad, különben végrehajtja rá a prímtesztet és "prime" vagy "not prime" sztringet írja ki a standard kimenetre. >millerrabinC.exe too little parameters >millerrabinC.exe 42 25 too many parameters >millerrabinC.exe 23413 not prime >millerrabinC.exe 234135 not prime

Az F# progam fordításához a parancssorból meg kell hívni az fsc parancsot a forrás fájlra. >fsc -o fermatF.exe FermatF.fs 54

A program egy parancssori argumentumot vár. Ha több argumentum van csak az els˝ot veszi, ha hiányzik az argumentum kezeletlen kivétellet dob, különben végrehajtja rá a prímtesztet és "prime" vagy "not prime" sztringet írja ki a standard kimenetre. >fermatF.exe Unhandled Exception: System.Exception: No integer argument given at FermatF.Program () [0x00000] in :0 at <StartupCode$fermatF>.$fermatF.main@ () [0x00000] in :0 >fermatF.exe 23 78 prime >fermatF.exe 23413 not prime >fermatF.exe 234135 not prime

A Haskell program futtatásához meg kell hívni a ghc parancsot a forrás fájlra az alábbi paraméterekkel. >ghc --make millerrabinH.hs -o millerrabinH Chasing modules from: millerrabinH.hs Compiling Main

( millerrabinH.hs, millerrabinH.o )

Linking ...

A program egy parancssori argumentumot vár. Ha több vagy kevesebb argumentum van, hibát ad, különben végrehajtja rá a prímtesztet és "prime" vagy "not prime" sztringet írja ki a standard kimenetre.

55

>millerrabinH.exe 23413 not prime >millerrabinH.exe 234135 not prime

56

3. fejezet Az eredmények összegzése A dolgozat egy nagyobb lélegzet˝u kutatás kezdeti részének tekinthet˝o. Célja, hogy felmérje, hogy a kiválasztott programozási nyelvek mennyire felelnek meg prímtesztek megírására. Ebben a dolgozatban f˝oleg a programozási nyelvek vizsgálatára koncentráltam, nem pedig az algoritmusok hatékonyságának az összehasonlítására, mivel ezt már sokan elemezték. Természetesen a kutatás kés˝obbi szakaszában fontos lesz az is, hogy milyen nagyságrand˝u számokkal dolgozunk. Ekkor az algoritmusokat másképp fogjuk megválasztani. A dolgozat során teljesített tevékenységeim: • Ahhoz, hogy a feladatot elvégezzem, több programozási nyelv elemzésére volt szükség. A programozási nyelvek paradigmái, tulajdonságai és eszköztárai alapján döntöttem a C++, F és a Haskell programozási nyelv mellett. • A kutatás els˝o szakaszában egyszer˝u prímteszteket terveztem implementálni, így az elméleti háttér, gyakorlati használat és a meglév˝o algoritmusok elemzése után a naiv módszer, Fermat-prímteszt és a Miller-Rabin prímteszt mellett döntöttem. • Végrehajtottam a prímteszt algoritmusok implementálását a kiválasztott nyelveken. Kisebb problémák megoldására a nyelv által nyújtott lehet˝o legjobb eszközöket használtam. • A dolgozat további eredményeként teszteltem és elemeztem a programokat és kifejtettem az implementáció közben felmerült ötleteket a további kutatáshoz. Az eredményeket a tesztelési folyamat elvégzése után értékeltem ki. A tesztelési folyamat a futtatható állományok többszöri lefuttatásával történt. A programokat különkülön több mint 100 különböz˝o adatra teszteltem segéd tesztkörnyezet felhasználásával. A tesztelés eredményei: • A C++ és F# BigInteger könyvtárai hiányosak. Az egész számok gyökvonás m˝uvelete hiányzik a könyvtárakból, habár sok módszer van hatékony gyökszámító 57

algoritmusok implementálására. Ezen kívül az F# BigInteger könyvtára nem tartalmazott moduláris hatványozás m˝uveletet. • Továbbá, a C++ rand() és az F# Rand.Next() függvényei csak int32 típusú véletlen számokat tudtak generálni. A prímtesztek csak pozitív egész számokon m˝uködnek, így a 32 bites el˝ojeles egész számok korlátozzák a C++-ban és F-ban implementált és véletlen generátort használt programok bemen˝o paramétereinek a méretét. • Mind a három nyelvben sok esetben a nagy számokat kezel˝o könyvtárak eszköztára b˝o, viszont az eszközök megvalósítása egy másik típuson megírt hasonló m˝uvelettel történik. A típuskülönbségeket típuskonverziókkal oldják meg. Ez egy nagy hátrány, mert a típuskonverziók költséges m˝uveletek. Ezen kívül a tetsz˝olegesen nagy számok (BigIntek) használatát korlátozzák a változók méretbeli megkötésével. A C++ és F# is rendelkezik a prímtesztek implementálásához szükséges tulajdonságokkal és eszközökkel, de az eredmények alapján a Haskell programozási nyelv támogatja leginkább a prímtesztek kényelmes, gyors és hatékony implementálását.

3.1.

Jöv˝obeli tervek

Munkám további célja a más, gyakorlatban használt programozási nyelvek prímtesztek támogatására összpontosult elemzése (Java, C, kriptográfia DSL-ek ...), továbbá speciális gyors algoritmussal implementált m˝uveletek megvalósítása, és összetettebb prímtesztek implementálása a kiválasztott programozási nyelvekben.

3.2.

Hasonló kutatások

A dolgozatomhoz hasonló munkát Phillip Trelford valósított meg, aki kriptográfiai algoritmusok implementálását hasonlított össze C++, C#, F# és Haskell programozási nyelveken [15].

3.3.

Köszönetnyilvánítás

Ezúton mondok köszönetet Dr. Farkas Gábornak a dolgozat elkészítéséhez nyújtott segítségéért, valamint a TÁMOP-4.2.1/B-09/1/KMR-2010-0003 pályázatnak.

58

Irodalomjegyzék [1] Fekete Balázs – Kétszeri Dávid – Kecskés Katalin – Krázli Zoltán – Lakner Zoltán – Vatai Krisztina: Nyomon követés globális szabványokkal. 2007, GSI Magyarország. ISBN 9789630626477. [2] Blog: Project euler problem, 2010. http://freelancersunite.net/tag/ fsharp-powerpack/. [3] Jack W. Crenshaw: Integer square roots, 2010. http://www.embedded.com/ 98/9802fe2.htm. [4] Nikolaos Diamantis: Introduction to number theory, 2010. http://www.maths. nott.ac.uk/personal/pmznd/. [5] Farkas Gábor: Algebrai geometriai számítások. Eötvös Loránd Tudomány Egyetem, 2008. [6] Farkas Gábor – Fülöp Ágnes – Gonda János – Járai Antal – Kovács Attila – Láng Csabáné – Székely Jen˝o: Bevezetés a matematikába. 2005, ELTE Eötvös Kiadó. [7] Ivanyos Gábor – Rónyai Lajos – Kása Zoltán – Csörnyei Zoltán – Gács Péter – Farkas Gábor – Kátai

Imre – Burkhard

Englert – Dorius

Kawalski – Grzegorz

Male-

wicz – Alehander Shvartsman – Horváth Zoltán – Tejfel Máté – Illés Tibor – Nagy Marianna – Terlaki Tamás – Lakatos László – Szeidl László – Telek Miklós – Imreh Csanád – Bodon Ferenc – Fogaras Dániel – Lukács András – Demetrovics János – Sali Attila – Kiss Attila: Informatikai Algoritmusok 2. kötet. 2005, ELTE Eötvös Kiadó. ISBN 9634637752. [8] HaskellWiki:

Research

papers,

2010.

http://www.haskell.org/

haskellwiki/Research_papers. [9] Donald E. Knuth: The art of computer programming. 1998, Addison-Wesley. [10] Matt McCutchen: C++ big integer library, 2010. http://mattmccutchen. net/bigint/. 59

[11] Gyula Nagy: Digitális jelfeldolgozó algoritmusok teljesítményének mérése és optimalizálása. Diplomaterv (Eötvös Loránd Tudomány Egyetem). 2010. [12] Richard G. E. Pinch: Mathematics research page, 2010. http://www. chalcedon.demon.co.uk/rgep/rcam.html. [13] Bjarne Stroustrup: An Overview of the C++ Programming Language. 1998, AT&T Laboratories. [14] Don Syme – Adam Granicz – Antonio Cisternino: Expert F# (Expert’s Voice in .Net). 2007, Apress. ISBN 1590598504, 9781590598504. [15] Phillip Trelford: C++ vs C# vs F# vs Haskell, 2009. http://www.trelford. com/blog/post/C2b2b-vs-C-vs-F-vs-Haskell.aspx. [16] Kása Zoltán – Járai Antal – Kovács Attila – Jörg Rothe – Gyires Tibor – Iványi Antal – Klaudia Leopold – Eberhard Zehendner – Szidarovszky Ferenc – Vízvári Béla – Ulrich Tamm – Balogh Ádám – Demetrovics János – Sali Attila – Miklós István – Ingo Althöfer – Stefan Schwartz – Szirmányi_Kalos László – Elek István – Sidló Csaba – Galántai Aurél – Jeney András: Informatikai Algoritmusok 1. kötet. 2005, ELTE Eötvös Kiadó. ISBN 9634637752.

60