You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

91 lines
1.7 KiB

пре 3 година
  1. import random, sys
  2. def miller_rabin_pass(a, s, d, n):
  3. '''
  4. n is an odd number with
  5. n-1 = (2^s)d, and d odd
  6. and a is the base: 1 < a < n-1
  7. returns True iff n passes the MillerRabinTest for a
  8. '''
  9. a_to_power = pow(a, d, n)
  10. i=0
  11. #Invariant: a_to_power = a^(d*2^i) mod n
  12. # we test whether (a^d) = 1 mod n
  13. if a_to_power == 1:
  14. return True
  15. # we test whether a^(d*2^i) = n-1 mod n
  16. # for 0<=i<=s-1
  17. while(i < s-1):
  18. if a_to_power == n - 1:
  19. return True
  20. a_to_power = (a_to_power * a_to_power) % n
  21. i+=1
  22. # we reach here if the test failed until i=s-2
  23. return a_to_power == n - 1
  24. def miller_rabin(n):
  25. '''
  26. Applies the MillerRabin Test to n (odd)
  27. returns True iff n passes the MillerRabinTest for
  28. K random bases
  29. '''
  30. #Compute s and d such that n-1 = (2^s)d, with d odd
  31. d = n-1
  32. s = 0
  33. while d%2 == 0:
  34. d >>= 1
  35. s+=1
  36. #Applies the test K times
  37. #The probability of a false positive is less than (1/4)^K
  38. K = 20
  39. i=1
  40. while(i<=K):
  41. # 1 < a < n-1
  42. a = random.randrange(2,n-1)
  43. if not miller_rabin_pass(a, s, d, n):
  44. return False
  45. i += 1
  46. return True
  47. def gen_prime(nbits):
  48. '''
  49. Generates a prime of b bits using the
  50. miller_rabin_test
  51. '''
  52. while True:
  53. p = random.getrandbits(nbits)
  54. #force p to have nbits and be odd
  55. p |= 2**nbits | 1
  56. if miller_rabin(p):
  57. return p
  58. break
  59. def gen_prime_range(start, stop):
  60. '''
  61. Generates a prime within the given range
  62. using the miller_rabin_test
  63. '''
  64. while True:
  65. p = random.randrange(start,stop-1)
  66. p |= 1
  67. if miller_rabin(p):
  68. return p
  69. break
  70. if __name__ == "__main__":
  71. if sys.argv[1] == "test":
  72. n = sys.argv[2]
  73. print (miller_rabin(n) and "PRIME" or "COMPOSITE")
  74. elif sys.argv[1] == "genprime":
  75. nbits = int(sys.argv[2])
  76. print(gen_prime(nbits))