Miller–Rabin primality test: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
(Replace `for r` loop with `repeat` loop, since `r` is not used in loop body.) |
||
| Line 15: | Line 15: | ||
''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 |
||
''' |
'''repeat''' ''s'' − 1 times: |
||
''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'' |
||