Miller-Rabin Primality Test in python: Why I keep getting decimal.Overflow: [<class 'decimal.Overflow'>]?

I was trying to do the Miller-Rabin Primality Test in python. I've written the code like below based on pseudocode on Wikipedia:

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

But when I run the code and enter a prime number like 5336101, I got the following error:

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')

So I decide to use the Decimal module, modified a few lines of code:

• Adding part:

from decimal import Decimal  #Adding
from decimal import Context  #Adding

• Modifying part:

    for i in range(k):

        a = random.randint(2, n-1)
        t = Decimal(Decimal(a)**Decimal(d))
        x = Decimal(t) % n

But then I got another error:

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: [<class 'decimal.Overflow'>]

How can I fix this?

Apparently you are using Python 3 where x / y always returns a float even if the operand types are both int. float is limited in what it can represent to an overflow error can occur. In order to perform integer division you can use x // y. Specifically in your code the line s /= 2 should be changed to s //= 2.