




def 							UpperCAmelCase		(		snake_case			:					Tuple      ,       snake_case			:					List[Any] = 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 > 3317044064679887385961981 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:Any									=  [
					    2047,
					    1373653,
					    25326001,
					    3215031751,
					    2152302898747,
					    3474749660383,
					    341550071728321,
					    1,
					    3825123056546413051,
					    1,
					    1,
					    318665857834031151167461,
					    3317044064679887385961981,
					]

					_lowerCAmelCase:Any									=  [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:str									=  primes[:idx]
															break
					_lowerCAmelCase: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:
										_lowerCAmelCase:Any									=  False
										for r in range(snake_case    ):
															_lowerCAmelCase:List[Any]									=  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:Optional[Any]									=  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 							UpperCAmelCase		(		):
					assert not miller_rabin(561    )
					assert miller_rabin(563    )
					# 2047

					assert not miller_rabin(838201    )
					assert miller_rabin(838207    )
					# 1_373_653

					assert not miller_rabin(17316001    )
					assert miller_rabin(17316017    )
					# 25_326_001

					assert not miller_rabin(3078386641    )
					assert miller_rabin(3078386653    )
					# 3_215_031_751

					assert not miller_rabin(1713045574801    )
					assert miller_rabin(1713045574819    )
					# 2_152_302_898_747

					assert not miller_rabin(2779799728307    )
					assert miller_rabin(2779799728327    )
					# 3_474_749_660_383

					assert not miller_rabin(113850023909441    )
					assert miller_rabin(113850023909527    )
					# 341_550_071_728_321

					assert not miller_rabin(1275041018848804351    )
					assert miller_rabin(1275041018848804391    )
					# 3_825_123_056_546_413_051

					assert not miller_rabin(79666464458507787791867    )
					assert miller_rabin(79666464458507787791951    )
					# 318_665_857_834_031_151_167_461

					assert not miller_rabin(552840677446647897660333    )
					assert miller_rabin(552840677446647897660359    )
					# 3_317_044_064_679_887_385_961_981
					# upper limit for probabilistic test


if __name__ == "__main__":
				test_miller_rabin()












"""simple docstring"""






import baseaa





def 							UpperCAmelCase		(		snake_case			:					str    ):
					return baseaa.aaaencode(string.encode('''utf-8'''    )    )





def 							UpperCAmelCase		(		snake_case			:					bytes    ):
					return baseaa.aaadecode(snake_case    ).decode('''utf-8'''    )


if __name__ == "__main__":
				import doctest

				doctest.testmod()






