Tietojenkäsittelyteoria, kevät 2000
Harjoitus 9, to 23.3. klo 10-12 sali MaD381

1. Osoita, että universaalihajautusta käytettäessä minkä tahansa avaimen x kanssa törmäävien muiden avainten määrän odotusarvo on alle 1.
2. Hajautin on täydellinen joukolle , jos kaikilla , , on . Osoita, että jos , |S| = n, on esitettävien avainten joukko ja hajautin valitaan satunnaisesti jostakin universaalista hajautinperheestä, niin todennäköisyys että h on itse asiassa täydellinen joukolle S on vähintään .
3. Testaa ainakin 75% varmuudella onko 103 alkuluku, käyttäen (a) Solovayn-Strassenin, (b) Millerin-Rabinin algoritmia.
4. Toinen seuraavista tehtävistä:
   1. Osoita, että jos n>2 on pariton yhdistetty luku, niin todennäköisyys että Solovayn-Strassenin testi kelpuuttaa sen ``mahdollisena alkulukuna'' on alle 1/2.
   2. Osoita, että jos n>4 on pariton yhdistetty luku, niin todennäköisyys että Millerin-Rabinin testi kelpuuttaa sen ``mahdollisena alkulukuna'' on alle 1/2.
   (Kirjallisuuden käyttö tämän tehtävän apuna on sallittua ja suotavaa. Molempia testejä käsitellään ainakin teoksissa Knuth, Seminumerical Algorithms ja von zur Gathen & Gerhard, Modern Computer Algebra. Solovayn-Strassenin testin oikeellisuustodistus, joka on helpompi, löytyy useista muistakin lähteistä, esim. Motwani & Raghavan, Randomized Algorithms ja Salomaa, Public Key Cryptography.)
5. Osoita, että jos , niin . (Vihje: SATin totuusarvoasetuksen oikeellisuuden voi tarkastaa.)

Huom.: Yliopiston rehtorinvaalin takia kurssilla ei ole luentoa torstaina 23.3.