





import timeit



class 				_UpperCamelCase       :

       def __init__(		self:			Any       , _SCREAMING_SNAKE_CASE:			List[Any]		)							->			Optional[Any]:




              """simple docstring"""


              if isinstance(_SCREAMING_SNAKE_CASE       , _SCREAMING_SNAKE_CASE		):  # Initializes a matrix identical to the one provided.
                     UpperCamelCase_ 							=	arg
                     UpperCamelCase_ 							=	len(_SCREAMING_SNAKE_CASE		)
              else:  # Initializes a square matrix of the given size and set values to zero.
                     UpperCamelCase_ 							=	arg
                     UpperCamelCase_ 							=	[[0 for _ in range(self.n		)] for _ in range(self.n		)]



       def __mul__(		self:			Union[str, Any]       , _SCREAMING_SNAKE_CASE:			List[str]		)							->			Dict:




              """simple docstring"""


              UpperCamelCase_ 							=	Matrix(self.n		)
              for i in range(self.n		):
                     for j in range(self.n		):
                            for k in range(self.n		):
                                   matrix.t[i][j] += self.t[i][k] * b.t[k][j]
              return matrix




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_	)  ->		Optional[Any]:
       UpperCamelCase_ 							=	Matrix([[1, 0], [0, 1]]	)
       while b > 0:
              if b & 1:
                     matrix *= a
              a *= a
              b >>= 1
       return matrix




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_	)  ->		Union[str, Any]:
       # Trivial Cases
       if n == 1:
              return fa
       elif n == 2:
              return fa
       UpperCamelCase_ 							=	Matrix([[1, 1], [1, 0]]	)
       UpperCamelCase_ 							=	modular_exponentiation(UpperCamelCase_       ,		n - 2	)
       return fa * matrix.t[0][0] + fa * matrix.t[0][1]




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_	)  ->		List[Any]:
       # Trivial Cases
       if n == 1:
              return fa
       elif n == 2:
              return fa

       UpperCamelCase_ 							=	fa
       UpperCamelCase_ 							=	fa
       n -= 2

       while n > 0:
              UpperCamelCase_							,			UpperCamelCase_ 							=	fn_a + fn_a, fn_a
              n -= 1

       return fn_a




def 			lowerCAmelCase_			(				)  ->		Optional[int]:
       UpperCamelCase_ 							=	"\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
       UpperCamelCase_ 							=	"fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
       UpperCamelCase_ 							=	timeit.timeit(setup=UpperCamelCase_       ,		stmt=UpperCamelCase_       ,		number=100	)
       print("With matrix exponentiation the average execution time is "       ,		exec_time / 100	)
       return exec_time




def 			lowerCAmelCase_			(				)  ->		Tuple:
       UpperCamelCase_ 							=	"\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
       UpperCamelCase_ 							=	"simple_fibonacci(randint(1,70000), 1, 1)"
       UpperCamelCase_ 							=	timeit.timeit(setup=UpperCamelCase_       ,		stmt=UpperCamelCase_       ,		number=100	)
       print(
           "Without matrix exponentiation the average execution time is "       ,		exec_time / 100	)
       return exec_time




def 			lowerCAmelCase_			(				)  ->		List[Any]:
       matrix_exponentiation_time()
       simple_fibonacci_time()


if __name__ == "__main__":
     main()








from __future__ import annotations




def 			lowerCAmelCase_			(				UpperCamelCase_	)  ->		int | None:
       for r in range(1       ,		UpperCamelCase_	):
              UpperCamelCase_ 							=	[]
              for x in range(n - 1	):
                     UpperCamelCase_ 							=	pow(UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_	)
                     if val in li:
                            break
                     li.append(UpperCamelCase_	)
              else:
                     return r
       return None


if __name__ == "__main__":
     _UpperCAmelCase										=					int(input('Enter a prime number q: '))
     _UpperCAmelCase										=					find_primitive(q)
     if a is None:
          print(f'''Cannot find the primitive for the value: {a!r}''')
     else:
          _UpperCAmelCase										=					int(input('Enter private key of A: '))
          _UpperCAmelCase										=					pow(a, a_private, q)
          _UpperCAmelCase										=					int(input('Enter private key of B: '))
          _UpperCAmelCase										=					pow(a, b_private, q)

          _UpperCAmelCase										=					pow(b_public, a_private, q)
          _UpperCAmelCase										=					pow(a_public, b_private, q)

          print('The key value generated by A is: ', a_secret)
          print('The key value generated by B is: ', b_secret)

