b'\n_START_ARTICLE_\nMiller-Rabin-priemgetaltest\n_START_PARAGRAPH_\nDe Miller-Rabin-priemgetaltest of Rabin-Miller-priemgetaltest is een priemgetaltest: een algoritme dat bepaalt of een gegeven getal priem is of niet. Het is vergelijkbaar met de priemtest van Fermat en de Solovay-Strassen-priemgetaltest, die net als de Miller-Rabin-priemgetaltest veelal worden gebruikt in de cryptografie. De originele versie van deze test is gemaakt door Gary L. Miller en is deterministisch. Het deterministische deel van deze test is echter afhankelijk van de nog onbewezen Riemann-hypothese. Michael O. Rabin heeft de test veranderd tot een probabilistische test, die nergens van afhankelijk is en altijd werkt.\n_START_SECTION_\nTheorie\n_START_PARAGRAPH_\nHet principe van de Miller-Rabin-priemgetaltest is hetzelfde als dat van de Fermattest en de Solovay-Strassen-priemgetaltest: van een of meer eigenschappen  van priemgetallen wordt nagegaan of het te testen getal deze eigenschap of eigenschappen heeft. Is dit niet het geval, dan is het getal geen priemgetal. Is het wel het geval, dan kan alleen geconcludeerd worden dat het getal mogelijk (waarschijnlijk) een priemgetal is.\n_START_SECTION_\nAlgoritme\n_START_PARAGRAPH_\nHet algoritme kan in pseudocode als volgt worden beschreven:_NEWLINE_Invoer: n\xc2\xa0>\xc2\xa02, een oneven geheel getal dat getest wordt voor primaliteit; k, een geheel getal dat de nauwkeurigheid van de test bepaalt_NEWLINE_Uitvoer: samengesteld als n samengesteld is, anders waarschijnlijk priem_NEWLINE_   schrijf n\xe2\x88\x921 als 2\xcb\xa2\xc2\xb7d met d oneven door machten van 2 uit n\xe2\x88\x921 weg te delen_NEWLINE_   LOOP: herhaal k keer:_NEWLINE_      kies 2\xc2\xa0\xe2\x89\xa4\xc2\xa0a\xc2\xa0\xe2\x89\xa4\xc2\xa0n\xe2\x88\x922 willekeurig_NEWLINE_      x\xc2\xa0\xe2\x86\x90\xc2\xa0a\xe1\xb5\x88 mod n_NEWLINE_      x\xc2\xa0=\xc2\xa01 of x\xc2\xa0=\xc2\xa0n\xe2\x88\x921 dan doe de volgende LOOP_NEWLINE_      voor r\xc2\xa0=\xc2\xa01,...,s\xe2\x88\x921_NEWLINE_         x\xc2\xa0\xe2\x86\x90\xc2\xa0x\xc2\xb2 mod n_NEWLINE_         x\xc2\xa0=\xc2\xa01 dan uitvoer samengesteld_NEWLINE_         x\xc2\xa0=\xc2\xa0n\xe2\x88\x921 dan doe de volgende LOOP_NEWLINE_   uitvoer samengesteld_NEWLINE_uitvoer waarschijnlijk priem\n_START_SECTION_\nNauwkeurigheid\n_START_PARAGRAPH_\nZoals gezegd: voor hoe meer getallen a we de test uitvoeren, des te nauwkeuriger is de test. Het is bewezen dat voor elk oneven samengesteld getal n, ten minste 3/4 van de bases a getuigen zijn van het feit dat n samengesteld is. Dus als n samengesteld is, dan verklaart de Miller-Rabin priemgetaltest n als waarschijnlijk priem met kans hoogstens 4\xe2\x81\xbb\xe1\xb5\x8f. In dit opzicht verheft deze test zich boven de Solovay-Strassen priemgetaltest, want die verklaart een samengesteld getal als waarschijnlijk priem met kans hoogstens 2\xe2\x81\xbb\xe1\xb5\x8f.'