Miller Rabin

SUBMITTED BY: Guest

DATE: May 19, 2013, 4:02 a.m.

FORMAT: Python

SIZE: 724 Bytes

Raw Download

HITS: 2001

Report
  3. def exercise4 (n, k):
  4. ''' Miller-Rabin procedure '''
  5. d = n-1
  6. s = 0
  7. while d % 2 == 0 and d != 1:
  8. d = d//2
  9. s = s + 1
  11. while k > 0:
  12. k = k-1;
  13. a = random.randint(2, n-2)
  14. x = a**d % n #exercise3 (a,d,n)
  15. if x == 1 or x == n-1:
  16. continue
  17. list = range(1,s)
  18. for r in list:
  19. x = x**2 % n
  20. if x == 1:
  21. return "composite"
  22. if x == n-1:
  23. continue
  24. return "composite"
  25. return "prime"
comments powered by Disqus