






def    __lowerCAmelCase   (    __snake_case       ,			__snake_case = False							):
     if n == 2:
          return True
     if not n % 2 or n < 2:
          return False
     if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
          return False
     if n > 3_3170_4406_4679_8873_8596_1981 and not allow_probable:
          raise ValueError(
              "Warning: upper bound of deterministic test is exceeded. "
              "Pass allow_probable=True to allow probabilistic test. "
              "A return value of True indicates a probable prime."							)
     # array bounds provided by analysis
     __lowerCAmelCase             =       [
         2047,
         137_3653,
         2532_6001,
         32_1503_1751,
         2_1523_0289_8747,
         3_4747_4966_0383,
         341_5500_7172_8321,
         1,
         382_5123_0565_4641_3051,
         1,
         1,
         3186_6585_7834_0311_5116_7461,
         3_3170_4406_4679_8873_8596_1981,
     ]

     __lowerCAmelCase             =       [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
     for idx, _p in enumerate(__snake_case       ,			1							):
          if n < _p:
               # then we have our last prime to check
               __lowerCAmelCase             =       primes[:idx]
               break
     __lowerCAmelCase      ,			__lowerCAmelCase             =       n - 1, 0
     # break up n -1 into a power of 2 (s) and
     # remaining odd component
     # essentially, solve for d * 2 ** s == n - 1
     while d % 2 == 0:
          d //= 2
          s += 1
     for prime in plist:
          __lowerCAmelCase             =       False
          for r in range(__snake_case							):
               __lowerCAmelCase             =       pow(__snake_case       ,			d * 2**r       ,			__snake_case							)
               # see article for analysis explanation for m
               if (r == 0 and m == 1) or ((m + 1) % n == 0):
                    __lowerCAmelCase             =       True
                    # this loop will not determine compositeness
                    break
          if pr:
               continue
          # if pr is False, then the above loop never evaluated to true,
          # and the n MUST be composite
          return False
     return True





def    __lowerCAmelCase   (    ):
     assert not miller_rabin(561							)
     assert miller_rabin(563							)
     # 2047

     assert not miller_rabin(83_8201							)
     assert miller_rabin(83_8207							)
     # 1_373_653

     assert not miller_rabin(1731_6001							)
     assert miller_rabin(1731_6017							)
     # 25_326_001

     assert not miller_rabin(30_7838_6641							)
     assert miller_rabin(30_7838_6653							)
     # 3_215_031_751

     assert not miller_rabin(1_7130_4557_4801							)
     assert miller_rabin(1_7130_4557_4819							)
     # 2_152_302_898_747

     assert not miller_rabin(2_7797_9972_8307							)
     assert miller_rabin(2_7797_9972_8327							)
     # 3_474_749_660_383

     assert not miller_rabin(113_8500_2390_9441							)
     assert miller_rabin(113_8500_2390_9527							)
     # 341_550_071_728_321

     assert not miller_rabin(127_5041_0188_4880_4351							)
     assert miller_rabin(127_5041_0188_4880_4391							)
     # 3_825_123_056_546_413_051

     assert not miller_rabin(796_6646_4458_5077_8779_1867							)
     assert miller_rabin(796_6646_4458_5077_8779_1951							)
     # 318_665_857_834_031_151_167_461

     assert not miller_rabin(5528_4067_7446_6478_9766_0333							)
     assert miller_rabin(5528_4067_7446_6478_9766_0359							)
     # 3_317_044_064_679_887_385_961_981
     # upper limit for probabilistic test


if __name__ == "__main__":
 test_miller_rabin()














import numpy as np





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case       ,			__snake_case = 1E-12       ,			__snake_case = 100       ,			):
     assert np.shape(__snake_case							)[0] == np.shape(__snake_case							)[1]
     # Ensure proper dimensionality.
     assert np.shape(__snake_case							)[0] == np.shape(__snake_case							)[0]
     # Ensure inputs are either both complex or both real
     assert np.iscomplexobj(__snake_case							) == np.iscomplexobj(__snake_case							)
     __lowerCAmelCase             =       np.iscomplexobj(__snake_case							)
     if is_complex:
          # Ensure complex input_matrix is Hermitian
          assert np.array_equal(__snake_case       ,			input_matrix.conj().T							)

     # Set convergence to False. Will define convergence when we exceed max_iterations
     # or when we have small changes from one iteration to next.

     __lowerCAmelCase             =       False
     __lowerCAmelCase             =       0
     __lowerCAmelCase             =       0
     __lowerCAmelCase             =       1E12

     while not convergence:
          # Multiple matrix by the vector.
          __lowerCAmelCase             =       np.dot(__snake_case       ,			__snake_case							)
          # Normalize the resulting output vector.
          __lowerCAmelCase             =       w / np.linalg.norm(__snake_case							)
          # Find rayleigh quotient
          # (faster than usual b/c we know vector is normalized already)
          __lowerCAmelCase             =       vector.conj().T if is_complex else vector.T
          __lowerCAmelCase             =       np.dot(__snake_case       ,			np.dot(__snake_case       ,			__snake_case							)							)

          # Check convergence.
          __lowerCAmelCase             =       np.abs(lambda_ - lambda_previous							) / lambda_
          iterations += 1

          if error <= error_tol or iterations >= max_iterations:
               __lowerCAmelCase             =       True

          __lowerCAmelCase             =       lambda_

     if is_complex:
          __lowerCAmelCase             =       np.real(lambda_							)

     return lambda_, vector





def    __lowerCAmelCase   (    ):
     __lowerCAmelCase             =       np.array([[41, 4, 20], [4, 26, 30], [20, 30, 50]]							)
     __lowerCAmelCase             =       np.array([41, 4, 20]							)
     __lowerCAmelCase             =       real_input_matrix.astype(np.complexaaa							)
     __lowerCAmelCase             =       np.triu(1J * complex_input_matrix       ,			1							)
     complex_input_matrix += imag_matrix
     complex_input_matrix += -1 * imag_matrix.T
     __lowerCAmelCase             =       np.array([41, 4, 20]							).astype(np.complexaaa							)

     for problem_type in ["real", "complex"]:
          if problem_type == "real":
               __lowerCAmelCase             =       real_input_matrix
               __lowerCAmelCase             =       real_vector
          elif problem_type == "complex":
               __lowerCAmelCase             =       complex_input_matrix
               __lowerCAmelCase             =       complex_vector

          # Our implementation.
          __lowerCAmelCase      ,			__lowerCAmelCase             =       power_iteration(__snake_case       ,			__snake_case							)

          # Numpy implementation.

          # Get eigenvalues and eigenvectors using built-in numpy
          # eigh (eigh used for symmetric or hermetian matrices).
          __lowerCAmelCase      ,			__lowerCAmelCase             =       np.linalg.eigh(__snake_case							)
          # Last eigenvalue is the maximum one.
          __lowerCAmelCase             =       eigen_values[-1]
          # Last column in this matrix is eigenvector corresponding to largest eigenvalue.
          __lowerCAmelCase             =       eigen_vectors[:, -1]

          # Check our implementation and numpy gives close answers.
          assert np.abs(eigen_value - eigen_value_max							) <= 1E-6
          # Take absolute values element wise of each eigenvector.
          # as they are only unique to a minus sign.
          assert np.linalg.norm(np.abs(__snake_case							) - np.abs(__snake_case							)							) <= 1E-6


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 test_power_iteration()






