Anonymous user
Miller–Rabin primality test: Difference between revisions
m
more colors in pseudocode
m (→{{header|ALGOL 68}}: nl ww) |
m (more colors in pseudocode) |
||
Line 7:
'''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'' − 2]
''x'' ← ''a''<sup>''d''</sup> mod ''n''
'''if''' ''x'' = 1 or ''x'' = ''n'' − 1 '''then''' '''do''' '''next''' LOOP
'''for''' ''r'' = 1 .. ''s'' − 1
''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.
| |||