




from __future__ import annotations
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			Union[str, Any]:
							assert n > 1 and a > 0 and greatest_common_divisor(SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    ) == 1
							(lowercase__)  :	Union[str, Any]        =							extended_gcd(SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )  # Implemented below
							lowercase__  :	Dict        =							(b * s) % n
							return x
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			int:
							(lowercase__)  :	str        =							extended_euclid(SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )  # Implemented below
							if b < 0:
														lowercase__  :	Any        =							(b % n + n) % n
							return b
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			str:
							lowercase__  :	str        =							invert_modulo(SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )
							lowercase__  :	Dict        =							(b * s) % n
							return x
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			List[str]:
							assert a >= 0 and b >= 0

							if b == 0:
														lowercase__  :	List[Any]        =							a, 1, 0
							else:
														(lowercase__)  :	Any        =							extended_gcd(SCREAMING_SNAKE_CASE_    ,a % b    )
														lowercase__  :	Tuple        =							q
														lowercase__  :	List[str]        =							p - q * (a // b)

							assert a % d == 0 and b % d == 0
							assert d == a * x + b * y

							return (d, x, y)
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			Optional[int]:
							if b == 0:
														return (1, 0)
							(lowercase__)  :	int        =							extended_euclid(SCREAMING_SNAKE_CASE_    ,a % b    )
							lowercase__  :	Optional[int]        =							a // b
							return (y, x - k * y)
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			List[str]:
							if a < b:
														lowercase__  :	List[str]        =							b, a

							while a % b != 0:
														lowercase__  :	Dict        =							b, a % b

							return b


if __name__ == "__main__":
						from doctest import testmod

						testmod(name='''modular_division''', verbose=True)
						testmod(name='''modular_division2''', verbose=True)
						testmod(name='''invert_modulo''', verbose=True)
						testmod(name='''extended_gcd''', verbose=True)
						testmod(name='''extended_euclid''', verbose=True)
						testmod(name='''greatest_common_divisor''', verbose=True)





from __future__ import annotations

import math
import random
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			list[int]:
							lowercase__  :	List[Any]        =							d * e - 1
							lowercase__  :	Any        =							0
							lowercase__  :	Dict        =							0
							while p == 0:
														lowercase__  :	Dict        =							random.randint(2    ,n - 1    )
														lowercase__  :	int        =							k
														while True:
																					if t % 2 == 0:
																												lowercase__  :	str        =							t // 2
																												lowercase__  :	int        =							(g**t) % n
																												lowercase__  :	List[Any]        =							math.gcd(x - 1    ,SCREAMING_SNAKE_CASE_    )
																												if x > 1 and y > 1:
																																			lowercase__  :	Any        =							y
																																			lowercase__  :	Optional[int]        =							n // y
																																			break  # find the correct factors
																					else:
																												break  # t is not divisible by 2, break and choose another g
							return sorted([p, q]    )


if __name__ == "__main__":
						import doctest

						doctest.testmod()