


def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : list[int]      ,					SCREAMING_SNAKE_CASE__      : int    ):
       __UpperCamelCase   							=len(SCREAMING_SNAKE_CASE__    )
       __UpperCamelCase   							=[[False] * (required_sum + 1) for _ in range(arr_len + 1    )]

       # for each arr value, a sum of zero(0) can be formed by not taking any element
       # hence True/1
       for i in range(arr_len + 1    ):
              __UpperCamelCase   							=True

       # sum is not zero and set is empty then false
       for i in range(1      ,					required_sum + 1    ):
              __UpperCamelCase   							=False

       for i in range(1      ,					arr_len + 1    ):
              for j in range(1      ,					required_sum + 1    ):
                     if arr[i - 1] > j:
                            __UpperCamelCase   							=subset[i - 1][j]
                     if arr[i - 1] <= j:
                            __UpperCamelCase   							=subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

       return subset[arr_len][required_sum]


if __name__ == "__main__":
   import doctest

   doctest.testmod()









import os
import random
import sys

from . import cryptomath_module as cryptoMath  # noqa: N812
from . import rabin_miller as rabinMiller  # noqa: N812

def 						_UpperCAmelCase    (      ):
     print('Making key files...'    )
     make_key_files('rsa'      ,					10_24    )
     print('Key files generation successful.'    )

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : int    ):
     print('Generating prime p...'    )
     __UpperCamelCase   							=rabinMiller.generate_large_prime(SCREAMING_SNAKE_CASE__    )
     print('Generating prime q...'    )
     __UpperCamelCase   							=rabinMiller.generate_large_prime(SCREAMING_SNAKE_CASE__    )
     __UpperCamelCase   							=p * q

     print('Generating e that is relatively prime to (p - 1) * (q - 1)...'    )
     while True:
          __UpperCamelCase   							=random.randrange(2 ** (key_size - 1)      ,					2 ** (key_size)    )
          if cryptoMath.gcd(SCREAMING_SNAKE_CASE__      ,					(p - 1) * (q - 1)    ) == 1:
               break

     print('Calculating d that is mod inverse of e...'    )
     __UpperCamelCase   							=cryptoMath.find_mod_inverse(SCREAMING_SNAKE_CASE__      ,					(p - 1) * (q - 1)    )

     __UpperCamelCase   							=(n, e)
     __UpperCamelCase   							=(n, d)
     return (public_key, private_key)

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : str      ,					SCREAMING_SNAKE_CASE__      : int    ):
     if os.path.exists(F'{name}_pubkey.txt'    ) or os.path.exists(F'{name}_privkey.txt'    ):
          print('\nWARNING:'    )
          print(
              F'"{name}_pubkey.txt" or "{name}_privkey.txt" already exists. \n'
              'Use a different name or delete these files and re-run this program.'    )
          sys.exit()

     __UpperCamelCase							,				__UpperCamelCase   							=generate_key(SCREAMING_SNAKE_CASE__    )
     print(F'\nWriting public key to file {name}_pubkey.txt...'    )
     with open(F'{name}_pubkey.txt'      ,					'w'    ) as out_file:
          out_file.write(F'{key_size},{public_key[0]},{public_key[1]}'    )

     print(F'Writing private key to file {name}_privkey.txt...'    )
     with open(F'{name}_privkey.txt'      ,					'w'    ) as out_file:
          out_file.write(F'{key_size},{private_key[0]},{private_key[1]}'    )


if __name__ == "__main__":
   main()





