title: Miller-Rabin Primality Test in python: Why I keep getting decimal.Overflow: [<class 'decimal.Overflow'>]?
body: <p>I was trying to do the <a href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow noreferrer">Miller-Rabin Primality Test</a> in python. I've written the code like below based on <a href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Miller%E2%80%93Rabin_test" rel="nofollow noreferrer">pseudocode</a> on Wikipedia:</p>
  
  <pre><code>from math import *
  from numpy import *
  
  def Miller_Rabin(n, k):    #Miller-Rabin Primality Test
      if n == 2 or n == 3:
          return True
  
      if n % 2 == 0:
          return False
  
      s = n - 1
      d = 0
      r = 0
  
      while True:
          if s % 2 == 0:
              r += 1
              s /= 2
  
          else:
              d = s
              break
  
      for i in range(k):
  
          a = random.randint(2, n-1)
          t = a**d
          x = t % n
  
          if x == 1 or x == n-1:
              continue
  
          for j in range(r-1):
              x = x**2 % n
  
              if x == n-1:
                  continue
  
          return False
      return True
  </code></pre>
  
  <p>But when I run the code and enter a prime number like 5336101, I got the following error:</p>
  
  <pre><code>File "C:\Users\kienp\Documents\Math Projects\Primality Test\primality_test.py", line 46, in Miller_Rabin
      t = a**d
  OverflowError: (34, 'Result too large')
  </code></pre>
  
  <p>So I decide to use the Decimal module, modified a few lines of code:</p>
  
  <ul>
  <li><strong>Adding part:</strong></li>
  </ul>
  
  <pre><code>from decimal import Decimal  #Adding
  from decimal import Context  #Adding
  </code></pre>
  
  <ul>
  <li><strong>Modifying part:</strong></li>
  </ul>
  
  <pre><code>    for i in range(k):
  
          a = random.randint(2, n-1)
          t = Decimal(Decimal(a)**Decimal(d))
          x = Decimal(t) % n
  </code></pre>
  
  <p>But then I got another error:</p>
  
  <pre><code>File "C:\Users\kienp\Documents\Math Projects\Primality Test\primality_test.py", line 46, in Miller_Rabin
      t = Decimal(Decimal(a)**Decimal(d))
  decimal.Overflow: [&lt;class 'decimal.Overflow'&gt;]
  </code></pre>
  
  <p>How can I fix this? </p>