title: Having trouble getting Miller-Rabin primality test in Python
body: <p>I have been trying to implement Miller-Rabin primality test in Python. Unfortunately there seems to be a problem on some prime numbers. Any help is appreciated.</p>
  <p>Code:</p>
  <pre><code>def _isPrime(n):
  
  if n % 2 == 0:
      return False
  
  a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
  s, d = _Apart(n) # turns it into 2^s x d
  print(s, d)
  
  basePrime = False
  isPrime = True
  
  for base in a:
      if base &gt;= n-2:
          break 
  
      if isPrime == False and basePrime == False:
          return False
      
      witness = pow(base, d)
  
      if (witness % n) == 1 or (witness % n) == (n-1):
          basePrime = True
          continue
      else:
          basePrime = False
  
      for r in range(1, s):
          witness = pow(base, pow(2, r) * d)
  
          if (witness % n) != ( n - 1 ):
              isPrime = False
  
  return True
  </code></pre>
  <p>Test:</p>
  <pre><code>isPrime(17)
  </code></pre>
  <p>Expected:</p>
  <pre><code>True
  </code></pre>
  <p>Result:</p>
  <pre><code>False
  </code></pre>