Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import random, math
- def rabinMiller(num): # uses the Rabim-Miller algorith to determine if an integer is prime
- if num % 2 == 0 or num < 2:
- return False
- if num == 3:
- return True
- s = num - 1
- t = 0
- while s % 2 == 0: # keeps halving s until it is odd
- s = s // 2
- t += 1
- for trial in range(5):
- a = random.randrange(2, num - 1)
- v = pow(a, s, num) # a is the base, s is the exponent, num is the number used for modulus
- if v != 1: # test dos not apply is v is 1
- i = 0
- while v != (num - 1):
- if i == t - 1:
- return False
- else:
- i = i+1
- v=(v**2) % num
- return True
- print(rabinMiller(140978205131430057786686123475267577570390375344764587080760431809771530061910794793034025491595966658654904382987493016762669627760864075779436829744637280211114286749315113550675535228512694084687890626777559003562863196680957223867169934057416836892538002753755334038890846199603221290277003679346294970671))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement