Anonymous user
Miller–Rabin primality test: Difference between revisions
no edit summary
No edit summary |
|||
Line 8:
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'' −
''x'' ← ''a''<sup>''d''</sup> mod ''n''
'''if''' ''x'' = 1 or ''x'' = ''n'' − 1 '''then''' '''do''' '''next''' LOOP
| |||