Stochastische algoritmen en priemgetaltesten

Bas Ketsman, 18 juli 2011

Als thesisonderwerp voor het behalen van mijn diploma van academische bachelor in de informatica, koos ik voor het onderwerp stochastische algoritmen en priemgetaltesten. Gezien het gebruik van toevalsalgoritmen in mijn opleiding tot hier toe zo goed als niet aan bod kwam, leek dit het ideale moment om mij alsnog te verdiepen in de wereld van de kanstheorie en meer specifiek het gebruik ervan bij het ontwerp van algoritmen.

In deze blog-post geef ik een samenvatting van de behandelde onderwerpen en een overzicht van interessante lectuur.

Stochastische algoritmen

Mijn doel was het onderwerp op een theoretische manier te behandelen en dit door de meest fundamentele vragen rond het onderwerp trachten te beantwoorden. Enkele van deze vragen worden hieronder opgesomd.

Hoe kunnen verschillende stochastische algoritmen van elkaar worden onderscheidden, hoe kan de complexiteit van een stochastisch algoritme worden gemeten en in welke klassificatiesystemen resulteert dit.
Hoe kunnen we concreet, al dan niet vertrekkende van een bestaand deterministisch algoritme, een efficiënt stochastische algoritme ontwerpen?
Hoe kan een ondergrens worden berekend op de complexiteit van stochastische algoritmen voor een bepaald probleem?
Bestaan er standaard technieken die het analyseren van stochastische algoritmen kunnen vergemakkelijken?
Wat is toeval en hoe kan toeval worden geïmplementeerd op een deterministische machine?
Wanneer is toeval overbodig?

Stochastische priemgetaltesten

In het tweede deel van de thesis werd de werking van enkele stochastische priemgetaltesten toegelicht en geïmplementeerd. De reden waarom werd gekozen voor dit onderwerp is tweeledig. Enerzijds zijn de priemgetaltesten een schoolvoorbeeld van het nut van stochastische algoritmen. Hoewel er al lange tijd efficiënte stochastische priemgetaltesten bestaan, werd pas recent de eerste deterministisch polynomiale priemgetaltest ontwikkeld. Anderzijds berusten deze onderwerpen op getaltheoretische en algebraïsche begrippen, ideaal dus om ook hier wat meer over te leren. Onder de behandelde algoritmen behoren:

de Fermat test;
de Solovay-Strassen test; en
de Miller-Rabin test.

Interessante lectuur

Als rode draad werden onderstaande drie boeken gehanteerd. Natuurlijk aangevuld met allerhande papers en artikels.

[MR00]: R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 2000.
[HRO05]: J. Hromkovič. Design and analysis of randomized algorithms: introduction to design paradigms. Texts in theoretical computer science. Springer-Verlag, 2005.
[DIE04]: M. Dietzfelbinger. Primality Testing in Polynomial Time From Randomized Algorithms to “PRIMES is in P”. Springer-Verlag, 2004.

Stochastische algoritmen en priemgetaltesten