



def  lowerCAmelCase_	(lowerCAmelCase__:		int		,						lowerCAmelCase__:		bool = False  ):





			"""simple docstring"""


			if n == 2:
						return True
			if not n % 2 or n < 2:
						return False
			if n > 5 and n % 1_0 not in (1, 3, 7, 9):  # can quickly check last digit
						return False
			if n > 3_3_1_7_0_4_4_0_6_4_6_7_9_8_8_7_3_8_5_9_6_1_9_8_1 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
			UpperCAmelCase_:		Union[str, Any]							      =     [
			    2_0_4_7,
			    1_3_7_3_6_5_3,
			    2_5_3_2_6_0_0_1,
			    3_2_1_5_0_3_1_7_5_1,
			    2_1_5_2_3_0_2_8_9_8_7_4_7,
			    3_4_7_4_7_4_9_6_6_0_3_8_3,
			    3_4_1_5_5_0_0_7_1_7_2_8_3_2_1,
			    1,
			    3_8_2_5_1_2_3_0_5_6_5_4_6_4_1_3_0_5_1,
			    1,
			    1,
			    3_1_8_6_6_5_8_5_7_8_3_4_0_3_1_1_5_1_1_6_7_4_6_1,
			    3_3_1_7_0_4_4_0_6_4_6_7_9_8_8_7_3_8_5_9_6_1_9_8_1,
			]

			UpperCAmelCase_:		List[Any]							      =     [2, 3, 5, 7, 1_1, 1_3, 1_7, 1_9, 2_3, 2_9, 3_1, 3_7, 4_1]
			for idx, _p in enumerate(lowerCAmelCase__		,						1  ):
						if n < _p:
									# then we have our last prime to check
									UpperCAmelCase_:		List[Any]							      =     primes[:idx]
									break
			UpperCAmelCase_      ,							UpperCAmelCase_:		List[Any]							      =     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:
						UpperCAmelCase_:		List[Any]							      =     False
						for r in range(lowerCAmelCase__  ):
									UpperCAmelCase_:		List[Any]							      =     pow(lowerCAmelCase__		,						d * 2**r		,						lowerCAmelCase__  )
									# see article for analysis explanation for m
									if (r == 0 and m == 1) or ((m + 1) % n == 0):
												UpperCAmelCase_:		Union[str, 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  lowerCAmelCase_	():





			"""simple docstring"""


			assert not miller_rabin(5_6_1  )
			assert miller_rabin(5_6_3  )
			# 2047

			assert not miller_rabin(8_3_8_2_0_1  )
			assert miller_rabin(8_3_8_2_0_7  )
			# 1_373_653

			assert not miller_rabin(1_7_3_1_6_0_0_1  )
			assert miller_rabin(1_7_3_1_6_0_1_7  )
			# 25_326_001

			assert not miller_rabin(3_0_7_8_3_8_6_6_4_1  )
			assert miller_rabin(3_0_7_8_3_8_6_6_5_3  )
			# 3_215_031_751

			assert not miller_rabin(1_7_1_3_0_4_5_5_7_4_8_0_1  )
			assert miller_rabin(1_7_1_3_0_4_5_5_7_4_8_1_9  )
			# 2_152_302_898_747

			assert not miller_rabin(2_7_7_9_7_9_9_7_2_8_3_0_7  )
			assert miller_rabin(2_7_7_9_7_9_9_7_2_8_3_2_7  )
			# 3_474_749_660_383

			assert not miller_rabin(1_1_3_8_5_0_0_2_3_9_0_9_4_4_1  )
			assert miller_rabin(1_1_3_8_5_0_0_2_3_9_0_9_5_2_7  )
			# 341_550_071_728_321

			assert not miller_rabin(1_2_7_5_0_4_1_0_1_8_8_4_8_8_0_4_3_5_1  )
			assert miller_rabin(1_2_7_5_0_4_1_0_1_8_8_4_8_8_0_4_3_9_1  )
			# 3_825_123_056_546_413_051

			assert not miller_rabin(7_9_6_6_6_4_6_4_4_5_8_5_0_7_7_8_7_7_9_1_8_6_7  )
			assert miller_rabin(7_9_6_6_6_4_6_4_4_5_8_5_0_7_7_8_7_7_9_1_9_5_1  )
			# 318_665_857_834_031_151_167_461

			assert not miller_rabin(5_5_2_8_4_0_6_7_7_4_4_6_6_4_7_8_9_7_6_6_0_3_3_3  )
			assert miller_rabin(5_5_2_8_4_0_6_7_7_4_4_6_6_4_7_8_9_7_6_6_0_3_5_9  )
			# 3_317_044_064_679_887_385_961_981
			# upper limit for probabilistic test


if __name__ == "__main__":
	test_miller_rabin()











from typing import TYPE_CHECKING

from ...utils import _LazyModule


a      :  int			     =			{'tokenization_wav2vec2_phoneme': ['Wav2Vec2PhonemeCTCTokenizer']}


if TYPE_CHECKING:
	from .tokenization_wavaveca_phoneme import WavaVecaPhonemeCTCTokenizer
else:
	import sys

	a      :  int			     =			_LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)






