import random


def _choose_bases(n):
    """Choose appropriate bases for the Miller-Rabin primality test.

    If n is small enough, returns a tuple of bases which are provably
    deterministic for that n. If n is too large, return a mostly random
    selection of bases such that the chances of an error is less than
    1/4**40 = 8.2e-25.
    """
    # The Miller-Rabin test is deterministic and completely accurate for
    # moderate sizes of n using a surprisingly tiny number of tests.
    # See: Pomerance, Selfridge and Wagstaff (1980), and Jaeschke (1993)
    # http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
    if n < 1373653:  # Blah, it's too hard to read big ints at a glance.
        # ~1.3 million
        bases = (2, 3)
    elif n < 9080191:  # ~9.0 million
        bases = (31, 73)
    elif n < 4759123141:  # ~4.7 billion
        # Note to self: checked up to approximately 394 million in 9 hours.
        bases = (2, 7, 61)
    elif n < 2152302898747:  # ~2.1 trillion
        bases = (2, 3, 5, 7, 11)
    elif n < 3474749660383:  # ~3.4 trillion
        bases = (2, 3, 5, 7, 11, 13)
    elif n < 341550071728321:  # ~341 trillion
        bases = (2, 3, 5, 7, 11, 13, 17)
    else:
        # n is too large, so we have to use a probabilistic test. There's no
        # harm in trying some of the lower values for base first.
        bases = (2, 3, 5, 7, 11, 13, 17) + tuple(
                    [random.randint(18, n-1) for _ in range(40)]
                    )
        # Note: we can always be deterministic, no matter how large N is, by
        # exhaustive testing against each i in the inclusive range
        # 1 ... min(n-1, floor(2*(ln N)**2)). We don't do this, because it is
        # expensive for large N, and of no real practical benefit.
    return bases