SHARE
TWEET

Untitled

a guest Feb 14th, 2020 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random, math
  2. def rabinMiller(num): # uses the Rabim-Miller algorith to determine if an integer is prime
  3.     if num % 2 == 0 or num < 2:
  4.         return False
  5.     if num == 3:
  6.         return True
  7.     s = num - 1
  8.     t = 0
  9.     while s % 2 == 0:  # keeps halving s until it is odd
  10.         s = s // 2
  11.         t += 1
  12.     for trial in range(5):
  13.         a = random.randrange(2, num - 1)
  14.         v = pow(a, s, num) # a is the base, s is the exponent, num is the number used for modulus
  15.         if v != 1: # test dos not apply is v is 1
  16.             i = 0
  17.             while v != (num - 1):
  18.                 if i == t - 1:
  19.                     return False
  20.                 else:
  21.                     i = i+1
  22.                     v=(v**2) % num
  23.     return True
  24.  
  25.  
  26. print(rabinMiller(140978205131430057786686123475267577570390375344764587080760431809771530061910794793034025491595966658654904382987493016762669627760864075779436829744637280211114286749315113550675535228512694084687890626777559003562863196680957223867169934057416836892538002753755334038890846199603221290277003679346294970671))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top