


def 				__lowerCamelCase						( UpperCAmelCase_						:		int ,  UpperCAmelCase_						:		bool = False						):




      """simple docstring"""





      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
      a						:Optional[int] 							=       [
          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,
      ]

      a						:List[Any] 							=       [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
      for idx, _p in enumerate(UpperCAmelCase_ ,  1						):
            if n < _p:
                  # then we have our last prime to check
                  a						:Optional[Any] 							=       primes[:idx]
                  break
      a							,				a						:Tuple 							=       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:
            a						:Optional[int] 							=       False
            for r in range(UpperCAmelCase_						):
                  a						:Optional[int] 							=       pow(UpperCAmelCase_ ,  d * 2**r ,  UpperCAmelCase_						)
                  # see article for analysis explanation for m
                  if (r == 0 and m == 1) or ((m + 1) % n == 0):
                        a						:int 							=       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						( ):




      """simple docstring"""





      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 string

import numpy
def 				__lowerCamelCase						( UpperCAmelCase_						:		int ,  UpperCAmelCase_						:		int						):




      """simple docstring"""





      return b if a == 0 else greatest_common_divisor(b % a ,  UpperCAmelCase_						)







class 		_snake_case  :
 SCREAMING_SNAKE_CASE__      =       string.ascii_uppercase + string.digits
 # This cipher takes alphanumerics into account
 # i.e. a total of 36 characters

 # take x and return x % len(key_string)
 SCREAMING_SNAKE_CASE__      =       numpy.vectorize(lambda _snake_case							: x % 36							)

 SCREAMING_SNAKE_CASE__      =       numpy.vectorize(_snake_case							)




 def __init__(		self					,  _lowerCamelCase    ):
       a						:List[Any] 							=       self.modulus(_lowerCamelCase    )  # mod36 calc's on the encrypt key
       self.check_determinant()  # validate the determinant of the encryption key
       a						:int 							=       encrypt_key.shape[0]




 def        SCREAMING_SNAKE_CASE__				(		self					,  _lowerCamelCase    ):
       return self.key_string.index(_lowerCamelCase    )




 def        SCREAMING_SNAKE_CASE__				(		self					,  _lowerCamelCase    ):
       return self.key_string[round(_lowerCamelCase    )]




 def        SCREAMING_SNAKE_CASE__				(		self    ):
       a						:str 							=       round(numpy.linalg.det(self.encrypt_key    )    )

       if det < 0:
             a						:Any 							=       det % len(self.key_string    )

       a						:Dict 							=       len(self.key_string    )
       if greatest_common_divisor(_lowerCamelCase					,  len(self.key_string    )    ) != 1:
             a						:int 							=       (
                 F'''determinant modular {req_l} of encryption key({det}) '''
                 F'''is not co prime w.r.t {req_l}.\nTry another key.'''
             )
             raise ValueError(_lowerCamelCase    )




 def        SCREAMING_SNAKE_CASE__				(		self					,  _lowerCamelCase    ):
       a						:Optional[Any] 							=       [char for char in text.upper() if char in self.key_string]

       a						:List[str] 							=       chars[-1]
       while len(_lowerCamelCase    ) % self.break_key != 0:
             chars.append(_lowerCamelCase    )

       return "".join(_lowerCamelCase    )




 def        SCREAMING_SNAKE_CASE__				(		self					,  _lowerCamelCase    ):
       a						:Dict 							=       self.process_text(text.upper()    )
       a						:List[str] 							=       ''''''

       for i in range(0					,  len(_lowerCamelCase    ) - self.break_key + 1					,  self.break_key    ):
             a						:int 							=       text[i : i + self.break_key]
             a						:Optional[int] 							=       [self.replace_letters(_lowerCamelCase    ) for char in batch]
             a						:Union[str, Any] 							=       numpy.array([vec]    ).T
             a						:str 							=       self.modulus(self.encrypt_key.dot(_lowerCamelCase    )    ).T.tolist()[
                 0
             ]
             a						:List[Any] 							=       ''''''.join(
                 self.replace_digits(_lowerCamelCase    ) for num in batch_encrypted    )
             encrypted += encrypted_batch

       return encrypted




 def        SCREAMING_SNAKE_CASE__				(		self    ):
       a						:List[Any] 							=       round(numpy.linalg.det(self.encrypt_key    )    )

       if det < 0:
             a						:int 							=       det % len(self.key_string    )
       a						:Tuple 							=       None
       for i in range(len(self.key_string    )    ):
             if (det * i) % len(self.key_string    ) == 1:
                   a						:Tuple 							=       i
                   break

       a						:List[str] 							=       (
           det_inv
           * numpy.linalg.det(self.encrypt_key    )
           * numpy.linalg.inv(self.encrypt_key    )
       )

       return self.to_int(self.modulus(_lowerCamelCase    )    )




 def        SCREAMING_SNAKE_CASE__				(		self					,  _lowerCamelCase    ):
       a						:List[Any] 							=       self.make_decrypt_key()
       a						:str 							=       self.process_text(text.upper()    )
       a						:List[Any] 							=       ''''''

       for i in range(0					,  len(_lowerCamelCase    ) - self.break_key + 1					,  self.break_key    ):
             a						:Optional[Any] 							=       text[i : i + self.break_key]
             a						:List[Any] 							=       [self.replace_letters(_lowerCamelCase    ) for char in batch]
             a						:str 							=       numpy.array([vec]    ).T
             a						:Dict 							=       self.modulus(decrypt_key.dot(_lowerCamelCase    )    ).T.tolist()[0]
             a						:List[Any] 							=       ''''''.join(
                 self.replace_digits(_lowerCamelCase    ) for num in batch_decrypted    )
             decrypted += decrypted_batch

       return decrypted







def 				__lowerCamelCase						( ):




      """simple docstring"""





      a						:Tuple 							=       int(input('''Enter the order of the encryption key: '''						)						)
      a						:Dict 							=       []

      print('''Enter each row of the encryption key with space separated integers'''						)
      for _ in range(UpperCAmelCase_						):
            a						:List[str] 							=       [int(UpperCAmelCase_						) for x in input().split()]
            hill_matrix.append(UpperCAmelCase_						)

      a						:Any 							=       HillCipher(numpy.array(UpperCAmelCase_						)						)

      print('''Would you like to encrypt or decrypt some text? (1 or 2)'''						)
      a						:Any 							=       input('''\n1. Encrypt\n2. Decrypt\n'''						)
      if option == "1":
            a						:str 							=       input('''What text would you like to encrypt?: '''						)
            print('''Your encrypted text is:'''						)
            print(hc.encrypt(UpperCAmelCase_						)						)
      elif option == "2":
            a						:Dict 							=       input('''What text would you like to decrypt?: '''						)
            print('''Your decrypted text is:'''						)
            print(hc.decrypt(UpperCAmelCase_						)						)


if __name__ == "__main__":
     import doctest

     doctest.testmod()

     main()





