Next: About this document
Up: No Title
Previous: No Title
-
Osoita, että universaalihajautusta käytettäessä minkä tahansa
avaimen x kanssa törmäävien muiden avainten määrän
odotusarvo on alle 1.
-
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 .
-
Testaa ainakin 75% varmuudella onko 103 alkuluku,
käyttäen (a) Solovayn-Strassenin, (b) Millerin-Rabinin
algoritmia.
-
Toinen seuraavista tehtävistä:
-
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.
-
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.) -
Osoita, että jos , niin .
(Vihje: SATin totuusarvoasetuksen oikeellisuuden
voi tarkastaa.)
Huom.:
Yliopiston rehtorinvaalin takia kurssilla ei ole luentoa torstaina 23.3.
Pekka Orponen
Thu Mar 16 23:18:01 EET 2000