Paste: 1

from os import urandom
from gmpy2 import *
from random import *
from Crypto.Util.number import *
from sympy import nextprime
import itertools

n = 11994856154408832550226173326306706948322784186267813285424273727457277570449721708469377333295795450316798985747411428007939478275824993378444272641075595828905331211398917692117185101479077398613046411577116685482608874046448872880344276808220924860769086887940958633441714352583855540999548720044322998264846012161431636662433683276562625027092028130005970114647137832180580174041968866569822387764690463959881397320450667236461741620403395599935845735617477280364151807003271533625363666352062617204207977554178272479567385510394164676984094113453536958667301026374275130979677305822214444335545662001110540052205079456125870487695548122936396959457217914532553325619253546791069692985512699358985463221502502084675209516472887973080192751916784600603877788797705458888760552581342959043655183973152680603248917128462709597030509958883674860205970644241146476304149515438669191043736965162506814748737378119531830170603146515955648287154128232624377713379199023238511614078806426562021069638546292232028008642595243475950555611966843590609370802372713922810842109296634261927855897749685466429848085401683729949137325841031448197225286597985926477607730381020542179177937190267395728321154320663113144417493792344192501728192224067408526468047697092815734745508911899235305415196605573552817031582341240841963500082141599736527564221706520431869455796746093434293683100803464504347573705307339278622142604231243731290546424726300181230919587809100360017180646300141932273203009540779621343752276406327270280696985946756857577522536182716290889259854732662916401670054957144740292721681742707739784073111634648716873018489059318376430379543710047917376490266767875239644497833040110744093598044604501318749065110017000755265530585848590714646543215789831321305186253110749828658194624302871154167229533880360661192631336611540590753329799514109722282049242508985274973975569128167197103339329219857542511675333185438424100205435264185442625212957816223665085393904833681032006083319868956112013073947804141313761890184012761243094669629438534487954505709858329677691050279420667276012005715403824771026942764503867179041742712964566104284721980020875049780798089586557353746689141977077518535458410939575796862938638716615803650407786897854972763793186411099146552957299304020322056573695947636353479929828321017230745880492761198924142557387134524722498789054500072958840330107186959238787198423202007480930533185363864760876539962555722806312411851288978109934860380767506470800563090423502953911794718800665163227148855219153379250626032923411536090260611564327090513624773651630139865213054047971676969921132075382597029378871818496911936273603167169708274436918974731159618512856370147955309970639864283488998194291564522716718108808644500794139567941894324821270494322487330771480736023069465090696594967014241811185428807158275522064429448212412679526940639213423056138417455582473816078505889037913398303842261835933581251153905467725831957314379762137644348555546053964035105996510374509932329977348336229876173135652873412359763033310447686419768148309532098091688546115562450592460242975433396729597685387307
c = 6351466082405672614085883295737944548919965310077599978190541984976106721260561511854691553565453868610374663116381728992690135579603964052096888436742489466374210302988977830209354260009636769071300547671488922280932487568494617872097079900945916095578623755388259234178268680612477377610914894710907496104362972636720911428089600646222586417255348258167381366988661303295347517753632411800607422746813905818666335896482669033027140915808983428842744482539062142710596639786508537317845758580996627882525064014450135034588736834794180287554486686075596972841883555087846775677701021701479352637748421102843822406248351476994277131337482690575095175009349909732516378330382964315421709620022837911961196685966020194554189215141758762297821318628808131301398323401698864010506849785816316875321330260285263314080063147494581040037600990836748077720670885523772728159627902311960453296092752330952130969249700776559562104117567236854526041303478039102747984668480082877982578911506991928425276445385557957750379045259124494960054574534424135407768648703579640630316936268243612044686186580389257001065198441757102217761322659630686894710273768219013265353821348563879078174064695595467864392947552655739896949699714908310000268044992892911329386425950830381092394869669909772028429264943114745575587790304248788515785473427021962255432027331143994772029825798100553275968616702208346511746136952846098000483881079268476334708733720366718979528049610330304650435684527462122705466063185641405473474636409990254433154961156119876528578589683787745161026307683732723150673756819990500536505419317277397641638885910418427679382912218056162106726030182041543254191389196695732924652812425467589000461451026805090543916784702340460053504268171601901665797607174213052404647848620139395976717777302984408101541424736063698589129484369980805581194717731469528976219054596456039278307705269184407577544084520370372269984748277291765285669123103849832742912650693589627527731652063314823281800811899078839130817382422516706798968876936676146422986085568876006217756879288536420625765537735876869140624480292479927568778211793082812927301155660252404197005435807632705417486828432680003527496336100268260013505692287715197974824293602702048074200039989010466046954319001764702167525159391165221097412507207070941040169607617565907669448292394080513719952028379907211892278587213063509785161727181094780834140425449087027374354210627478929892809387327800956442381416648762382930744745836860691652645272468710801480127383690670796702340344827232853798294566232977982518551989524593975440927239406568783391313258506866750608077495352966704970278327215482373252538685185523964815393905211818152851498336930972438448603569283564012724941434639295494863634240132261738242762708931234148319337032370483580480928554288281017282842715728356865227629594590080908396457555253561758256890799884600635571737440212394730433411857064284860111226945575837832906205884951631607279348335031910003072824224574236747404904434087096197641226369055991560801425685762426000158519701843480002622016573514879915173451468691465801627597331478760735200706227052
e = 14338839073210349887787514275814499181389923069109753825994309046402251

def pre(limit):
    primes = [2]
    while primes[-1] < limit:
        primes += [nextprime(primes[-1])]
    return primes

def my_factor(n, p):
    global primes

    p_list, alpha_list = [], []
    
    for i in range(50):
        p = nextprime(p)
        cnt = 0
        while (n % p == 0):
            cnt += 1
            n //= p
        if (cnt != 0):
            p_list.append(p)
            alpha_list.append(cnt)

    print(n)   

    return p_list, alpha_list

def find_phi(ps, alphas, e):
    phi = 1
    for p, alpha in zip(ps, alphas):
        cur_ = (p-1) * p ** (alpha-1)
        phi *= cur_
    return phi

primes = pre(100)
ps, alphas = my_factor(n, 2 ** 128)
# print(ps)
# print(alphas)
es, betas = my_factor(e, 1)
phi = find_phi(ps, alphas, e)
g, a1, a2 = xgcd(e, phi)
print(g)
mm = pow(c, a1, n)

palphas = [p ** alpha for p, alpha in zip(ps, alphas)]
ms = []

for palpha in palphas:
    Zn = Zmod(palpha)
    m2 = Zn(mm)
    m1 = m2.nth_root(g, all=True)
    ms.append(map(int, m1))

for i in itertools.product(*ms):
    m = crt(list(i), palphas)
    # print(pow(m, e, n) - c)
    m = long_to_bytes(m)
    if (b'flag' in m):
        print(m.encode('hex'))

# flag{you_ave_s0_cute_to_join_this_gam3~}