Miller-Rabin算法

 

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·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]
   xad mod n
   if x = 1 or x = n − 1 then do next LOOP
   for r = 1 .. s − 1
      xx2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next LOOP
   return composite
return probably prime

One thought on “Miller-Rabin算法

  1. digiter

    我上学期为准备比赛看的《计算数论》,讲这些东西讲得挺好的

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *