docs: def is_prime( n ):
    """Return True if x is prime, False otherwise.
  
    We use the Miller-Rabin test, as given in Menezes et al. p. 138.
    This test is not exact: there are composite values n for which
    it returns True.
  
    In testing the odd numbers from 10000001 to 19999999,
    about 66 composites got past the first test,
    5 got past the second test, and none got past the third.
    Since factors of 2, 3, 5, 7, and 11 were detected during
    preliminary screening, the number of numbers tested by
    Miller-Rabin was (19999999 - 10000001)*(2/3)*(4/5)*(6/7)
    = 4.57 million.
    """
  
    # (This is used to study the risk of false positives:)
    global miller_rabin_test_count
  
    miller_rabin_test_count = 0
  
    if n <= smallprimes[-1]:
      if n in smallprimes: return True
      else: return False
  
    if gcd( n, 2*3*5*7*11 ) != 1: return False
  
    # Choose a number of iterations sufficient to reduce the
    # probability of accepting a composite below 2**-80
    # (from Menezes et al. Table 4.4):
  
    t = 40
    n_bits = 1 + int( math.log( n, 2 ) )
    for k, tt in ( ( 100, 27 ),
                   ( 150, 18 ),
                   ( 200, 15 ),
                   ( 250, 12 ),
                   ( 300,  9 ),
                   ( 350,  8 ),
                   ( 400,  7 ),
                   ( 450,  6 ),
                   ( 550,  5 ),
                   ( 650,  4 ),
                   ( 850,  3 ),
                   ( 1300, 2 ),
                   ):
      if n_bits < k: break
      t = tt
  
    # Run the test t times:
  
    s = 0
    r = n - 1
    while ( r % 2 ) == 0:
      s = s + 1
      r = r // 2
    for i in range( t ):
      a = smallprimes[ i ]
      y = modular_exp( a, r, n )
      if y != 1 and y != n-1:
        j = 1
        while j <= s - 1 and y != n - 1:
          y = modular_exp( y, 2, n )
          if y == 1:
            miller_rabin_test_count = i + 1
            return False
          j = j + 1
        if y != n-1:
          miller_rabin_test_count = i + 1
          return False
    return True