Jupyter Notebook Viewer (original) (raw)

def is_prime(p, witnesses=50): # witnesses is a parameter with a default value. ''' Tests whether a positive integer p is prime. For p < 2^64, the test is deterministic, using known good witnesses. Good witnesses come from a table at Wikipedia's article on the Miller-Rabin test, based on research by Pomerance, Selfridge and Wagstaff, Jaeschke, Jiang and Deng. For larger p, a number (by default, 50) of witnesses are chosen at random. ''' if (p%2 == 0): # Might as well take care of even numbers at the outset! if p == 2: return True else: return False

if p > 2**64:  # We use the probabilistic test for large p.
    trial = 0
    while trial < witnesses:
        trial = trial + 1
        witness = randint(2,p-2) # A good range for possible witnesses
        if Miller_Rabin(p,witness) == False:
            return False
    return True

else:  # We use a determinisic test for p <= 2**64.
    verdict = Miller_Rabin(p,2)
    if p < 2047:
        return verdict # The witness 2 suffices.
    verdict = verdict and Miller_Rabin(p,3)
    if p < 1373653:
        return verdict # The witnesses 2 and 3 suffice.
    verdict = verdict and Miller_Rabin(p,5)
    if p < 25326001:
        return verdict # The witnesses 2,3,5 suffice.
    verdict = verdict and Miller_Rabin(p,7)
    if p < 3215031751:
        return verdict # The witnesses 2,3,5,7 suffice.
    verdict = verdict and Miller_Rabin(p,11)
    if p < 2152302898747:
        return verdict # The witnesses 2,3,5,7,11 suffice.
    verdict = verdict and Miller_Rabin(p,13)
    if p < 3474749660383:
        return verdict # The witnesses 2,3,5,7,11,13 suffice.
    verdict = verdict and Miller_Rabin(p,17)
    if p < 341550071728321:
        return verdict # The witnesses 2,3,5,7,11,17 suffice.
    verdict = verdict and Miller_Rabin(p,19) and Miller_Rabin(p,23)
    if p < 3825123056546413051:
        return verdict # The witnesses 2,3,5,7,11,17,19,23 suffice.
    verdict = verdict and Miller_Rabin(p,29) and Miller_Rabin(p,31) and Miller_Rabin(p,37)
    return verdict # The witnesses 2,3,5,7,11,17,19,23,29,31,37 suffice for testing up to 2^64.