

import random



def       __lowerCAmelCase      (						A    ):
	UpperCAmelCase_       				=			num - 1
	UpperCAmelCase_       				=			0

	while s % 2 == 0:
		UpperCAmelCase_       				=			s // 2
		t += 1

	for _ in range(5    ):
		UpperCAmelCase_       				=			random.randrange(2       ,     num - 1    )
		UpperCAmelCase_       				=			pow(A       ,     A       ,     A    )
		if v != 1:
			UpperCAmelCase_       				=			0
			while v != (num - 1):
				if i == t - 1:
					return False
				else:
					UpperCAmelCase_       				=			i + 1
					UpperCAmelCase_       				=			(v**2) % num
	return True



def       __lowerCAmelCase      (						A    ):
	if num < 2:
		return False

	UpperCAmelCase_       				=			[
	    2,
	    3,
	    5,
	    7,
	    11,
	    13,
	    17,
	    19,
	    23,
	    29,
	    31,
	    37,
	    41,
	    43,
	    47,
	    53,
	    59,
	    61,
	    67,
	    71,
	    73,
	    79,
	    83,
	    89,
	    97,
	    101,
	    103,
	    107,
	    109,
	    113,
	    127,
	    131,
	    137,
	    139,
	    149,
	    151,
	    157,
	    163,
	    167,
	    173,
	    179,
	    181,
	    191,
	    193,
	    197,
	    199,
	    211,
	    223,
	    227,
	    229,
	    233,
	    239,
	    241,
	    251,
	    257,
	    263,
	    269,
	    271,
	    277,
	    281,
	    283,
	    293,
	    307,
	    311,
	    313,
	    317,
	    331,
	    337,
	    347,
	    349,
	    353,
	    359,
	    367,
	    373,
	    379,
	    383,
	    389,
	    397,
	    401,
	    409,
	    419,
	    421,
	    431,
	    433,
	    439,
	    443,
	    449,
	    457,
	    461,
	    463,
	    467,
	    479,
	    487,
	    491,
	    499,
	    503,
	    509,
	    521,
	    523,
	    541,
	    547,
	    557,
	    563,
	    569,
	    571,
	    577,
	    587,
	    593,
	    599,
	    601,
	    607,
	    613,
	    617,
	    619,
	    631,
	    641,
	    643,
	    647,
	    653,
	    659,
	    661,
	    673,
	    677,
	    683,
	    691,
	    701,
	    709,
	    719,
	    727,
	    733,
	    739,
	    743,
	    751,
	    757,
	    761,
	    769,
	    773,
	    787,
	    797,
	    809,
	    811,
	    821,
	    823,
	    827,
	    829,
	    839,
	    853,
	    857,
	    859,
	    863,
	    877,
	    881,
	    883,
	    887,
	    907,
	    911,
	    919,
	    929,
	    937,
	    941,
	    947,
	    953,
	    967,
	    971,
	    977,
	    983,
	    991,
	    997,
	]

	if num in low_primes:
		return True

	for prime in low_primes:
		if (num % prime) == 0:
			return False

	return rabin_miller(A    )



def       __lowerCAmelCase      (						A = 1024    ):
	while True:
		UpperCAmelCase_       				=			random.randrange(2 ** (keysize - 1)       ,     2 ** (keysize)    )
		if is_prime_low_num(A    ):
			return num


if __name__ == "__main__":
				_a:    str 							=			generate_large_prime()
				print(("""Prime number:""", num))
				print(("""is_prime_low_num:""", is_prime_low_num(num)))


from __future__ import annotations

class 						__UpperCamelCase    :




	def __init__(		self	:						Optional[Any]		,	lowerCAmelCase	:						str		,	lowerCAmelCase	:						str							):


		'''simple docstring'''







		UpperCAmelCase_				,   UpperCAmelCase_       				=			text, pattern
		UpperCAmelCase_				,   UpperCAmelCase_       				=			len(lowerCAmelCase							), len(lowerCAmelCase							)




	def       __A					(		self	:						List[str]		,	lowerCAmelCase	:						str							):


		'''simple docstring'''







		for i in range(self.patLen - 1		,	-1		,	-1							):
			if char == self.pattern[i]:
				return i
		return -1




	def       __A					(		self	:						int		,	lowerCAmelCase	:						int							):


		'''simple docstring'''







		for i in range(self.patLen - 1		,	-1		,	-1							):
			if self.pattern[i] != self.text[current_pos + i]:
				return current_pos + i
		return -1




	def       __A					(		self	:						str							):


		'''simple docstring'''







		UpperCAmelCase_       				=			[]
		for i in range(self.textLen - self.patLen + 1							):
			UpperCAmelCase_       				=			self.mismatch_in_text(lowerCAmelCase							)
			if mismatch_index == -1:
				positions.append(lowerCAmelCase							)
			else:
				UpperCAmelCase_       				=			self.match_in_pattern(self.text[mismatch_index]							)
				UpperCAmelCase_       				=			(
				    mismatch_index - match_index
				)  # shifting index lgtm [py/multiple-definition]
		return positions


_a:    Dict 							=			"""ABAABA"""
_a:    Union[str, Any] 							=			"""AB"""
_a:    str 							=			BoyerMooreSearch(text, pattern)
_a:    Dict 							=			bms.bad_character_heuristic()

if len(positions) == 0:
				print("""No match found""")
else:
				print("""Pattern found in following positions: """)
				print(positions)