import binascii	
	

def string2int(my_str):
    return int(binascii.hexlify(my_str), 16) 

def int2string(my_int):
    return binascii.unhexlify(format(my_int, "x").encode("utf-8")).decode("utf-8")

###Function for the Extended Euclidean Algorithm
### X is the inverse of a mod b and Y is the inverse of b mod a
def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)
###Function to calculate the n-root of x such that y ** n <= x < (y + 1) ** n, so it returns an integer, not a float.
def find_invpow(x,n):
	high = 1
	while high ** n <= x:
		high = high *2
	low = high//2 ###Integer division, no float point
	while low < high:
		mid = (low + high) // 2
		if low < mid and mid**n < x:
		    low = mid
		elif high > mid and mid**n > x:
		    high = mid
		else:
		    return mid
	return mid + 1

n= 23516695565660963250242846975094031309572348962900032827958534374248114661507001374384417953124930587796472484525315334716723068326965228898857733318407681656604325744994115789416012096318656034667361976251100005599211469354510367804546831680730445574797161330145320706346512982316782618118878428893337849886890813813050423818145497040676697510093220374542784895778086554812954376689653727580227087363619223145837820593375994747273662064715654881379557354513619477314410917942381406981452545764657853425675230343749326640073923166795823683203941972393206970228647854927797483660176460658959810390117898333516129469397
e= 3

ciphertext = 145069245024457407970388457302568525045688441508350620445553303097210529802020156842534271527464635050860748816803790910853366771838992303776518246009397475087259557220229739272919078824096942593663260736405547321937692016524108920147672998393440513476061602816076372323775207700936797148289812069641665092971298180210327453380160362030493


### As M^e is lower than n, the message is just the e root of c
m = find_invpow(ciphertext,e)
message = int2string(m)
print (message)
