Miller–Rabin primality test: Difference between revisions

Content added Content deleted
m (more colors in pseudocode)
Line 7: Line 7:
'''Output''': ''composite'' if ''n'' is composite, otherwise ''probably prime''
'''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
write ''n'' − 1 as 2<sup>''s''</sup>·''d'' with ''d'' odd by factoring powers of 2 from ''n'' − 1
LOOP: repeat ''k'' times:
LOOP: '''repeat''' ''k'' times:
pick ''a'' randomly in the range [2, ''n'' − 2]
pick ''a'' randomly in the range [2, ''n'' − 2]
''x'' ← ''a''<sup>''d''</sup> mod ''n''
''x'' ← ''a''<sup>''d''</sup> mod ''n''
if ''x'' = 1 or ''x'' = ''n'' − 1 then do next LOOP
'''if''' ''x'' = 1 or ''x'' = ''n'' − 1 '''then''' '''do''' '''next''' LOOP
for ''r'' = 1 .. ''s'' − 1
'''for''' ''r'' = 1 .. ''s'' − 1
''x'' ← ''x''<sup>2</sup> mod ''n''
''x'' ← ''x''<sup>2</sup> mod ''n''
if ''x'' = 1 then return ''composite''
'''if''' ''x'' = 1 '''then''' '''return''' ''composite''
if ''x'' = ''n'' − 1 then do next LOOP
'''if''' ''x'' = ''n'' − 1 '''then''' '''do''' '''next''' LOOP
return ''composite
'''return''' ''composite''
return ''probably prime''
'''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.
* 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.
Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"