The [[wp:Miller–Rabin primality test|Miller–Rabin primality test]] or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not.

The algorithm, as modified by [[wp:Michael O. Rabin|Michael O. Rabin]] to avoid the [[wp:generalized Riemann hypothesis|generalized Riemann hypothesis]], is a probabilistic algorithm.

The pseudocode, from [[wp:Miller-Rabin primality test#Algorithm_and_running_time|Wikipedia]] is:
 '''Input''': ''n'' > 2, an odd integer to be tested for primality;
        ''k'', a parameter that determines the accuracy of the test
 '''Output''': ''composite'' if ''n'' is composite, otherwise ''probably prime''
 write ''n'' − 1 as 2<sup>''s''</sup>·''d'' with ''d'' odd by factoring powers of 2 from ''n'' − 1
 LOOP: '''repeat''' ''k'' times:
    pick ''a'' randomly in the range [2, ''n'' − 1]
    ''x'' ← ''a''<sup>''d''</sup> mod ''n''
    '''if''' ''x'' = 1 or ''x'' = ''n'' − 1 '''then''' '''do''' '''next''' LOOP
    '''repeat''' ''s'' − 1 times:
       ''x'' ← ''x''<sup>2</sup> mod ''n''
       '''if''' ''x'' = 1 '''then''' '''return''' ''composite''
       '''if''' ''x'' = ''n'' − 1 '''then''' '''do''' '''next''' LOOP
    '''return''' ''composite''
 '''return''' ''probably prime''

* The nature of the test involves big numbers, so the use of "big numbers" libraries (or similar features of the language of your choice) are suggested, but '''not''' mandatory.
* Deterministic variants of the test exist and can be implemented as extra (not mandatory to complete the task)
<br><br>