Challenge:

from Crypto.Util.number import *
from FLAG import flag
from random import randint

flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
ks = [randint(0, rr**(i+1)) for i in range(20)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n)
c2 = pow(flag, (1<<16)+1, n)
ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")



Solve:

Part 1 - solve the logs to get the ks

https://math.stackexchange.com/questions/1863037/discrete-logarithm-modulo-powers-of-a-small-prime

https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf


Part 2 is the franklin-reiter rsa attack.

from Crypto.Util.number import *
from tqdm import tqdm

ks = [70919577137553948225026829359952892017992369857129233935883277162711194324842921363974903163099339145663781137475483907364966326977551417231001550576764817820516163821184399579767358412593344390685967830624912399576493839556742404454603286678744840244326074550605619842953886917531674151849027712320806953974, 1586108873597391376836939152773916771199419430148746028994598635314207622876880309743918818337868362567381559351794167759189888511638843573658493573224872606875791806197785716699244941157408616339109560220419366940367073774670236004358536849619947730285579590276109244127957488346479731255052507957500475196663482736129905127061478659059965496695871052300679384505335339869571680122338240010854218887449488927419432924645685776896752663604190618459629585126636931, 16105249320854231353712056433168127388219050743196438394808578852514784890899470591687262701989809826051326776069638569543425789510695557187529156649045280567864308704983669242573659732021875485179423299316798511944581159478233194022428387179648163476227379501389407302369695382769632714814620098533469630829834526499732092025373129734207514222947986298511582213836146172336213933260310325360516978788241905234357736251842247806697950831919497545528932364337617791958596862379397335748596700536707937791600121022373841665060235247211427705387645938338412222076454395612365294533781738834482413165404129693091995737649, 68803785893095646291018085677204540454193293340202105548420563011725184276073469353439249315485845184249517440056499901708909757797682359771424715819571405205467882996453753399283594776434278871941932665157687945192811717684784271844454976066996087189664144128066230306970661296197739781242332248956094050494028108809702291817039062154908406188450313036861699383490036491717014319004697564507408149031832749463879053875905354398383980006790138563315800091434577297772230619313352414566500059714217289735686868117607117039064236691044052221098317597162101064805429905399575292444756519691758243289246266244254147267141395141498300191602730707656016596869247841502099400019261408016592445392739970382771631823810427698603156127755969621288063343264296795746377165374854146, 1086435820407082053696092455065855714644658146027569809978334216710020684638587028534314819312030439215953111354369099674373838918522792138476536153417064461459768484068178390824870529936133993668318781819652044212529732355921356304043998570573043842050148140863661377427269853520673433965456019087255580609833639804207010624795139217086363760135213125489091713906706097757660954665526764639180932120269491608840968758118167810492075744889422474852533899689942464403533891485166579890256441467378615277987544299103398986661269892041901056431601410883773820770109827286743447083409026860245509922459158108099893815351940303345927471488462328231358212689263799624029638146086814497672902922735732417842375825310866869265879971574011697623699126513575435491792349834690364537702633394602198365534362611967246255797092643731649541240870734686024696949651404201176829256656221708429594464515559310545508949564603991764490641142674, 28609232492396312935743850989010940611652842421660555622855351990396978406387028457650628985123620811235468274935572669724411891023143315183233627728957714354401533940681834966456776604187386524765527798089395166018941189443059739526606511963412857174702113533114349938228403169325242565014845032097151083542029960815674715700248304544505236018005378194025180906942570419435370695576161499949634230635551746926165557110860374112414090383920605205588740856500005618186246972231456570678464365331273467051595924449040329574571753265897464408871097615548050149699746704617652926188994105749189829550360217132831318050961371597154023088901604582548584294898932647764086215622590075859650073260435039277967092549765370236795949787991883324936339353623472562309089417091161146879593323222830096509580747355458046543563043334948823957347505908285850567608000385705235403664969720542312418189835060446004561901705681706312116426563462515273997775896879163283721268707758691555893430806802298978389864598611264948918292959498189343068790892695775215347420419467119438879898701927301606869, 191417841809872735054146655184512650098083726789767559817591892788038174397378953834495817796996284957501894288441008148397612383074280349701443335577799717053258077299534006085380559302673747925386918245066681576834137041095749332038353330585645180656054656489472256945293288666200340789172882405120456043990434640294964416374099721306113199958866994245919506128904422665371689236379907440548962545523404682095001292254826882461330681965063224441705966253886025512613127648615132746851029825614853302623452982966903869314675785895302662910074161998198916621112531107627623481472565967029401207761966265090626536144517030656081267415543811779720415102359344485132236715271755091025638448558016707084982114125369940233518851284778221830182802108489363182088230022786032593523363359661580034221193972144769858394597696874554891254394750771889443933840536157432802067771709659067883080122884610000331228087060807575707327755176739090571153604658341308954049003059383580774064963055701213142129175885433208390912829750669280383778028791133960269780159216051822061007566218659564809341109749775004565845588118274276291465933207543789351800827414670830089761319699102472010282122214147360722014317557663943262076671120974041614409458368389, 4304789707563337259810803922746754256091876355134356996759997600505561723288875563684547307156817226191351473706665959205224732847427878997834273793118458043999140891510796058401208465634686288162086185925182871752382730131945706500743680182230785260233894501009619281020694567496679065345097866719736117150568849818731880133710998784990616985923511874002221589529200129760976665462837856498784468525737217347202152169913627727174496288099010585937568663838423263255265609351864559392553496267551371972331076671847964714954122852083783123869220432296438358938094139688844778535776899028033325308996274341523384254986945959374461694249185740716922199777809197366235218226603444950643569187970155872972278468383726615580849671193094610721184099890573045285051170553508351269735472612322682796276557561903205969748402096188933652127089726737539989231549745480900375142076214299110324566402276851387690665164737187018201021673686918665665211416526254305256833561136150564149429321591201969362186709785526504319165743707276569038640516180340705643372712929171952510943871648132905304723947439548513016747136997255772779385556796190089311656001630992978578183210450813195209985914937741021520674341081432339360749895096368199987931163754876132489581396908106171771451664884357778296043065790545424953016182752302328100057011439139522567053735361749294823303989598990270462721441317382375041381, 17038958926285455544299337693983197384094856299956806606003289456852850879730590483285519606703579022386521143497011819316912064584729658026427110539315617230283868665576078459638619860092492584735387619990452249390194353185298454203653590076023324176951553561398691674916864932937894307360459739592355805043990587348221038110525573680488812750629648047235880656320512055286587954153157693091320506714520279640855258235109679442666214835982856678549358609166005962495812290769336495454119842682223241280912286031331748005669982365468092416744436510221600161902547601746120466492608779652532859895490033176865193407556189534659004897785751674274662362043008831937095174035856851303539154827665243232902174398468971673135836006392832146825262826456901504071160797970165670974117583856113885354061587985972571439359592540268330306544976666538899053837564023161771830858902956849163507715491211348474863914099173214009003604109994378358006374399305730783928103504930232504308427156078156569943633838533090687706000642284992907253640442821481380122374642477032169456966050888573659832537988575741591634739783906034948740683218935531542463117672237215670649690607404448935357892459915001327853837712861188831005110280220425257562531745785770688981266473523096390615139846343581936452716472120904428058786392446268146114767133550377556565428131734541353353145416738880516830139487858141854829879843122149755357370351238085049298862052731781606096395504815594413927240193138127132074836030642327831935137271682152549451006848723521340872121862045776, 223655710855739961286564415335195053402868745113261044098914825701135517676482696285031952948322574010215729351255910239375069379011868816734856611243723789275687858192302717042607918967245485050335279669885499835120486426276800029381220109037348715562138074561222821215334894122309703234824912840582194437870627976113153805766232638879001049571542945472836516863093691217863326410639680691871115787994712058281427443032070845080584112395857538058509780874700406111282162893372947211852683030793858205019084537987171038157739446975105255436416354848934359838155849941622358927313009530127835709577977990783506420443516394872932862627175716783791178417637305017123952549926808513925112135416915166213646845999736059022795930373076178279974448185960306023399066064655790100700493276109827644279572324655503823568012633856937701703304517255968668070933019224786822542200986300062324555457481628689023900329385872398607032536473924856644217750510990695844405080373191465174603057673174257302367274439245382649135715625822557424813823270412418013847776008275290127798569382290480916032000383681697980032123818714141884145229638065478540803408716075714926609812266232391357511580902228735010235539319733026858345316525071759867087651574043122216542726419754912599373929325061605474552803890639810124631115484489844536692635914410454978717064296802432217362619933991007221715074664068955849556513542815434424116989279100515724149334396921447061712158801487110379635187028759923934101802606319974466642788548143476623840862770682496620560683059631934719099179301602462121382804810286362726514654228725805631084427386299980640573931447237360918768862089785798050777127901758334547331804664874298989403554, 4761920524246169367580622962844432633118639431106791955659013266665183165806370527968984704438479383060767550866626163698038576313753430985927264339931030779198258709067793421848488493352467532191054142189156726257736795761832238654930492660022087326432205422463180979785138776343693690231961205340091997662281803906280510987307931773230667536651561681682730065010353741268348716872020899852916437220004846470241086029945093197282361522102191260194715051804490722175078373495609117329886316593665235897404091710521017844936698226441642185402258732609600239733690533925977234929526243734732271453530227625681297919745332179322081524837771426383315384946725904236637402148906040967090397635075057736298162926304530368288985586503090371382877921296286476263401303849592598332993482874235583165126624181330207781197494747073601091954350418939829953035484845248028441317772197357590654555164459898730981291052678658466616660019768079194412033261840671745526709782117382859711384050354747132694977554847517376591793241808317232619645368532308216325902531501024396593146726757675968352151919263485297244012234805401889527641181487727566781192856306185677858146101703860271997143943704360334049157612719266307534163530930437000385445798495557931948320319666983372207941100508173689280720138899633674060671787688676285633833615706342927378123557223606440144947716797630721169745221620747475672518024123337556459170992019534454231653118410142027490983522505835516697916547761761739799434920644649736704392571118749179379660829581424836853963135398977503449559267562506238451963214176615264353329366366000933515469183285035952746929376438583477105821917163549780939510917921610797615709675334419197922792559769340461600380753259412741266898379777155953771924286198848612699915756853813937744606485190333748760018823079128298458670728890633670929092964800036508, 1619584858941878762430473940096747748546598197705929364740537206711933130681646188982037753366854879340780434214601172194419584750370632177161867948075626205894859712413890562303660235400469652198218927878889142310525338756869309205312078331240205425016102329092387381850633555673392860150079383271838460863619153830676559248116567887187080007740373497955917117349248643311589497577041950358597208354318659397406255348147462039835727252285684153964889478900747105534651658626377876812380143310564159604832556994504530154079693951353461197927147973279020968615938773697076098717784080040549481992707904636249491865352006570079480743975331336087496743584137537057335412336274316996440087265539425898422178493079947902687491009899561576100739834701935115771583924080459780777927911347240117105944291584941778929524743065290029329913226896351403128214690567316711385990579873530477025379394678009712448144079902343766250836164950607429791339482693128720430661856339237065623198768556662223512768963828714387605468601211288606282381373683312004085502621584585256948444657682349817354825463391501392892055311008990286703324236739653577477990533584739153470882865942084741435039249371892141494398173801464794732963041792822143149974501213779801081326359251645084138059423478326076432773827127226856232347318751971625643023460956071068357649917824082253559904169166964552519712271675684420340925739991739032933647215354727105959242264136801756025408559691027405038763418963124403179853283186674285056284011401198118009024715424230849534739495749837925050486294653606905988718257037097894726472115832768580205712874214733398346393198850774258301101414212375301627233700103775434428080874197335506537593604808557791223416458603533024505293916782618671325542073368562530607537656473334637016609107850383548051883806422057683714655944505050716402521970970820246436139131238048777694168709356341372623024638131529091871639253333438166896760944645183826187445116069079723496828911913922255807222213189810074129958467, 398962149370138126899253400332789080370314499389058875688940442880253156700518541426014088432015869729610041714204683608584557043873015412693896804482546747127803370165130525315310371567322414728265410436172301777596227244189500078231681097921347921087308990249151707918735065866598529104382943742808232741741774501085461712371265127735951621501027997208923546323674948718279769658394153342858146775049208059140629980407033794665176924062649835033413819865217024966668988263139867819562075178268403137828878852910392747253934576565813357124109581475690728225450121657956256547631307668443024063482202187519645349180442201041611153852272474965779285876213889496082553856721336694287952017595572514632086812218379153068581534153297696738828794694465508313285196262932422046539810193313676432047447806618691874639492505161881956320109421457673777437519134818275980724761899452570021876167424126123476028669705357418205809062604166988043321755230178890106499337235237294666764578272751937786679763151518798250179354422935256119737199613010800039602004572044056591471079373506287376423056321207149931793134260346230047099190415131645649213047398807333470752873850299386372482714416199942814729359346578084246815034404511533657838216011835090907664451211116640930866613725761656004295906240443425001675677280245476367304136533600002207247552670992554778694258567062428265079483164447094118664681277968777745970677401277497975129699471193495683849157294722388264418815329536556416868257922066860016058453125368152486052608470261392104928177247967452420388785625719853851881621799428786356735223829409138068053183421645526715293362469602797973696571423747282268981525733016854796916878158547620492991316298974215216944545684592918741417531554680108468618513670291465417692594214789364280405519425776026914809770934103487705233613584685532315875321708474658496199741692901480149474320209544162090985147140459681327238538108572801304939018117180785150776115195123177537884255032093231401479210419340889571921083867623925354343272287156136634029657291652514933452017500125621273606551468310360278221194678861924849810415112284806720071932158456012987754157919560777202, 146988229050104926875833670889214090147000397427124952099047346002064676569102806270979611979709883382611323297759051410018814356478814953773427172601670367245464809918621225703977123247028642030387994577573841023151100509971130333090022014075421988077599406092813259184844241349092828320457860972913821321277156169777266947027735911770559491072896209879010877910528915832300763177291909858861775642800741882625594560527103883846796749425069117090768026349563754089994499925155548547386253907884558868555235001346105929420467917716292538452063752228124970813279617790071964805621778124279053225052138617744933960023132144265727131471470712083793020672454220707587140211514995310965570340827290133296801887197811181088199459662962806479086975776088535421966666072328662444839795704155009307458567770278339913793490518843227860471205383062662302322266204968503196777681440229341501642807072403928142860485409908808291168994236309834662133277162594619132069614934387345657152618710767723498230738704721959791763227044769676226548394868493249184253404636247186186447694981914563366310725253800040259121255838845464164535827713899987104564730517152850052576680985767739081253865871460386628544938271922048246281810413352083257852909909200637115972176348634288103636951682688044263030570548807622750571086317462714383145922232403173568433081500310693912466541069299389187941978078959626729458470099214583444708820159063314988973480141132235566735854824894593363164587902725091467638556908268918562227256221536490305641917658889197027978365294686527535161053066288978625387768517645568084814946669703655200933278539572205848783303465929654567161031877386574869929481471112683489695872991882164146029917137237646947492739895097220707544482552689107279182494599828051799956992061004696446386429893779804423742345900293332629482737909297351097104659601098992819554114891558875169954822466396690798552125500772676055809408560821673791493603067659941062344177917354428975226981269696504793572006911470954842741447872157680626185832600671527896428797596584211945380478262118044976209460463921804534976667851567468346596623595447440326150495326594952822206012607813129562221269890885827666057067949192324585833018224109963060009466194002073537793678599030596237338561583467939080179738805793499738021663971818934270224239368, 117440347873699781524105976847523938374653066702240273413866720941736067077086254218321499014932405324456724541687105116855976439881987617775286672517788462515590199758441969680992503605979474447170821598371258219024113401053368079127473201933829238966833560877112446176962003827856812963409356573060473154623854898519954904447184224488577281766280895966903203970394047253038843577651249806970707930013312392911096291171924220426206758834162367578422373003359397795596052363607700162442176658129506232819379737727805279925334089729206323752367855675671171522486230626555176039971966947598114735955425256776117865027327388063548574073509434523726950486194258905861335924284678977174149295244097561234499771020033779142964026267524680857080395291212960096031423630724157721949645661310650925755360924972399154871013382076115705860588819556139373742348787687456433289205742099946415267387961770073246593786983568393396251786093589350090537508983515353193015087214476268102508232136887357961330417124630684374092670987818335928145818602399409281753365003629756460593013518578602381782645864741102800959811484196657887833737262451819158354126102631283207570636727670421789544175009236402371447101512909910289272458352201505755381605931108670352340596761379575670757088296401174186140237627135398944380566591932960930772726945887189785011064643039934645658664020366466110908406691580801292961955325190917960180099233018419897506333544828568436120928412518450859423819768750504986330941435470612846709030192681019355861076962155774800716996631610850241414650448907886163582386579347382023368290769125734135461308910833828033895005366553039629741492365436485104618980167771206560641958015409459262393369667187522247963340058889542530135812513196747361254371193691802541310919087094546249411649663632312586141897286806630111839300800391949517340673160492984636912165987971966245673494253720910584319186588082749166875255588864858244735712789513300852454737120184599156339200076463674860738305810034043944644629006869247278412577114102974503426923083133198020079274857483280454783392916192477651996043999896852212873740740998668309242791043336807732888542043439240572298835432672412127655765633232074899960240652649161826548504488632610422267756011971750757060457048600235365355029955209305180846096609285801513640325924705489887227428581721962872172763004305359141915587679888275575058845725193069212046987640672801330498644844833670106519402809606457313947369243544577546302, 838008938974021347744246081242683076991744563163587402466348647979976338120651315375512115744986141797135951627279475063184670178055419509135466927744367115217000419967808595622711984796737413882943523657484999017063369255310712696271654365714668607649575424604397779492522698239362890980253502484850497787973225603494430069879407158126245876267963626839041580452314081277273250400233569707982361776994153421218491564630978307001890782691536693710121807755407008932839036217666589108188633444519100789393410997858606699793676213549330024247648781392100526194108756506738620353755633246188129008993897345901803003977673352841569149240171672858700692287126448571524617425808833826801212869513737196821415883987171582549714227725788502196700169833100435157495797871391735277045916979912616821887622216294734015292891864275932567027004357023840585191187912657334317755964804979593595842545442852771858603028008051898487501645985139732362875134274802537362981148561482409711127183773823476709173718104839480660626020108045033561572036558791229305250521043639755601637739854083344490551189586237652190124412726602148297599839649867063601562758497796700678519692713609785153365361685558068280029785267354932395867903908656138504248722552244674740585586996190955405057047089369961214626900687310374146708635745848954539061997819982824208550453343802939368112206964442760192427768699886492972371130377106716287672124411979644846848944207878636301740882060688972515181290640290141435120458947307343774578680596447797626392814686379089791645107371936985391452207093702112436404131410947458892480675240977619873580656911571315119468542375586810141845982659446938821102815054166396124278103419701371244558603866565749965098030601002706714668342531967192873591592232039951052833875179822608571451409779272294682105893249308864405569628761219201634553921973172579855913911460058782699490073415904563068227343232087330199357278249161293363027917407100536049996131226528247243208638089791750051604050799133801895067901231443312235220713904904773426566905198282656065765680498660348339706929057318466492572734533526859216925066333255309998283699925314974297140489428702191405598608343295190935247006532856188547313148920094269745151666214863262603123942875779548666067912954500200266282543158004853597440262667111191751237413729931179304302544165221186866457683778755320858140932138167695813292105681624844079958739318296521523014114808525304051401394039918004670416528309214011405109600909605035675822174898618652311385091756045642622886529319926790275600334584180260614772348123566679766324335871734602230147505887973136663993328153244, 16283029513858872607939884149497747442975093740757447104813706303663336753370540194530157039891804770254848672161639373429582626303963122764411871748091298613393387716958701275094201312766441765520025175356717965901695385533146663321646013811794032114030511303468940514362971201402934540647303838370196606312493927208305554538890964831508550886103034707350598676796292187297068363719976601820297002244113258194333326017731413596904623522615301610863741698852476355829739485368043550851558723915881103525513348926593881971313036496002461276185841258911584405097524891162478144685858453197207358186344300958635713364039955217631754072814655695403244554688709400338721248320875790259268866087893838619558842780779653549440267906938969527819878910355987914327548005183228659350928009406643783351863335700069622779820109223575884387855977791568860423676433399864470127612676678703467951069131790814771447471776484065613100046593134643978814046292846177346367012805941149355468976886816627898062664918478114532188403791190846633487738915056223100207736021832886863526962212736510280812198722985216952871853968061233195872291315697459461688409525486245017632573716142018625361329614508378465339103765721313154350758824662810251023539370837907647186107452432779338750229289494393749069685249893591637086608416200837065330836209355432716182418591261210086317580951657516627988435426608922763490933073855213169907254212888543107933442532904002380023645056478552807323278979357742949504591497796493238616296009548201630918455210521137145476279104170305794451963251239626132335404517611933750364228704706818028986052963944615862163686030471635801925945661861273335335066939686972228225344763596833233151635691855233783390134868727590166698343182033981496592740255233506257710598304191255740957108633659057870487901316050558566336149124208133267010844968069693844056597982833758674051400009800859290401809898759069276060510666252996698061207916388972944729897149365808771538833747367896836835704512657508499412464771828418680977008609856137333263325789736783578812711781993681395654139965395203823017517611802681368242297378071724880184148620550310441638496571363097066123271347766572388964947778786264992310117824895551169053637949847358773533584582352263173836194908413212709056359475605667489058167330900714483106437667468801678879338176410837490251836013111806029684166469061382563835655065458231266077766323044094033291850286568766400490320720705805450852111066246594065502202802745470872888478883886091975712616332144440373903918854983145560291043896868233756780202188106460732717655796746591458073983988913804906161562441211613932945437946173013828272555369168431801971267602332910118856519414745559617324649740764310136024128667082370290158703637035966205151131341048748835573355, 249520371263084037841738179882512904586153182079672925461414050331317855239306624996192770812737822998037800311408597496713168935908506284676562605929346211408534591372594118291442754172289181361032358754195206908345325588124357032112278925080146435932390899521411548375334576302956152016838931261001094646666917000881740377514070577538553773303867461475938645549329867997417461077010627748920313110658493709802441974051936285042613081140047308532091660800299505756394755271928637669600256812619323913049771546607857870478375965253929579609273900619029201477668308022579654567444665879549998024501927728502564349506747933745816945792694722062981013838027146068995833208849998730134020068068899878466030301945827465379273363750385146119145059616525902251956377621865964519015171405446293363413737205625733277727341120870442066424312432616099009536589831885032624581653158299027557492542530364186872932493337244304092811333535905882845818987116114709625956193031848399430072854927170410984618257069132741880561979847046362607309297454013761951362909285411883923538157242506492451027908090228059284578078081776724499685155036079832790576231618724027081148164917996318860308389490820174995475609215648498032536560233781064391055845143982475766057058417598407202033157112563901508925096018118813649996543735810889746515294744477497765745885345501118899939394569339633015340160305374085703515406597845331918105775068798010995301557436440300140454567646287311253570350555041214337592715544479671635857218944295500882552601496161357309353484073706506137114133381323409608036346080506775891189380519542919539978817403104817352607540600423633477339577691683029197051857254416817838515012316962097726861443428042787847073889540712503056820606277344781738873515415363697529172434945007443648628092955460263083713973840404208287829179321930516104056823858564186480108773740608359769134578453133732598242798340233032074821854435778632027403702300706502687761991906659366371923903817894636532641041318425881526004014484503932387676572246664286682034967967888745486046892647869477718607948589176453856806424114040627358815675127831463260636849042034567299041041961558047144430128833374561502685022776831945114285782012398315681022458090392641737668452273577674284896396916038392172277711689898229558394798826898537506977212831202527973928671813030779551714121610517030485624626732501230797402615468870603423061807113554530281723316446234900718936130988528217726417018023165744221351565499625661021385355373895505704213734528976513111098682560943099401065043067948063900855747701702312541118265175272904763229268229714518740248169140985487466457451971087678237289825809859945113957617377081747761520937748681135736760493307182074082066371784411353794590906010179391430505265611344250719249099724231311546773612035181034605428216644362330688139043378359908157851113484242396052695081252034203226409619809445389736297133274346335630470075320620068, 1653230148158065316185893361488318940512542937027670960446779165008561050733140882356408323912677950432807150122611774845709575219649487589710436624213303044211176057086687088378261682244021964620252096458643113161983440578119466517969740964024694558876937140281233276985811546333381757691776881478673793279475064945870938676889791917216814831911235066080515714456326379639338021637305425176969827007206174920775549396530519060893746596000455236062970725153269417758050254676258365035830707838757795252541242958024315775103457232372973463913116932926552675250276126108913364037881849770734138871848129934209742653306384116581554684028646514515686490762899884997132140550590990300558775030258653598185528500632046769370401102474218728720663287119970354218087563621915595269210055367946788454918360378813441506929603361774280929723465641673443910110080932446635554341206749571366536909750631156178471223034694623012758208835029572603359001726615644048065668042842721807340049737575378203166522049706734750599573299630446139608955965402672984682880796122332571764199000051910835168538152852755197140038482451357596209808376473025603381561359221681051142912578285735856039834893083202136427497003167580112221675995506830103761340424929937108380259302242577572012341925019880375040865352347223963479332125337256172996333975234273184070844075192653249844536533887003328118262967043688132033928635943746858378591286246398857952046925636515338820315847766527848433101448810475184494351568433307943757093252064970231984559771926223928021529915959538719881441271860862614392399384082186106768849671630763052457401524592617197984839717786615703308732716099385531927036821892526683344438405570940452601189388500140683214603356668592067706610566457660329866719557044808576045872085636848625754984446520478967868656221306525324724985560333801343122251449355577892274567863308881218021319809457426575440036046497944786702671783410656998549985067811214198578183611852182795465756929713301638155851846366353244524152464448068321731134504479000511137287952022114683883064602710346895107929516470853811050210754704296634844628426580755531025856167695200521743890421055748539801540916674373036949014409633083554107300021133055104550278398020856511487841507458352821584895923517248015338500956037890549046711860227724339729986866461315684553092717336523479980906898845118859435253560726581443406405103436458442807143986164037322743311859416077544468232670694682744055535398383487272658707284409357178368622861100040301468796985538467056308992972496558922974068487140259499921949120429894852066958384540527562247162635657079964039864385840948050939911577059661736328368126015105260088120097453278239806670035916642646219323688919166041266833509647222862961170041370320491957776063287169346079355354684252328654368254079893923923905303222452675933942180750923246922778429063479794286208269393032545554597872410355622548929363962300230214439474892319634809866716430178826920482392684422132590015992001982376989281414056054261329165862555688914385129660020664377023601869227374228875191872830727677252738686, 27583615506724225747830051756935229938586148196576320792583708307344659553091150651269734905391609244098852443503034249567271204789111004325879865208154128299074946814013530914017696992016057569444275793092254552858602061618364422984680500198059572027426694470413735782280125978746920240656236110492924612988374423559227225952575192265729052838753836856887375451193873376133663940906271761265282892640669483647056741624302784396931283368923136650155886034707608400321666627272211091036077975251846090492458939675745798682412788147848656430756228450757586754381875850324777976848089412000002244372771984223822227652790365006762551443165170750894204265294217459157426418077971337774542663480795656920193044321183576987159533813400456012528948291722330814452043863355578814074893791403512541277487382444975094340130390895619599810500228906129780449752710185676375746220816107878525517250026062996505619007128904013835173474391892879790204893705267961732299385445616116728057540242244493984614593483201727355738004586637950780594921802956174027211720737229595302726883654267488783871116858376457169583014487407193004969428473179007897477677094275873801494275806051275796718293137559167013212457042506921681914341481637872024054229564504852070851993173777160480794303640095704800501170963384863012181030133239620784593127247519418530763524660384457424478230421584868172744263274300772199956346331486149741040411008603729656493560280368801296329219355157492161238622838430364627874283024599781328118161237942006969419465463895773051452146937528978008580872310365022195456159125386279038276879709287021874123945790143866620173107847380376959771055196804791938641711065682937929720702895563544827290271433581313013154710576015528419447150443780830464934068467347511597680987086427206245371529441798559755855745959501008394659165512387107644169309425951950512252266431693723051466103248643011113878678031986911881678591864707042148361832515215656233301734129567244939175378984987846810436928473150486101927918046421636375466621605082111908243490147391601056641082958289801745453069567269885671464786571562697404293738806908944753477010911732717472309625695098340987054386631139705644553969839373595650292774149983411231092495245755166378056026626493662154767391087247525161828226370035897196258010494592885571954399143161944620066385578685093699711866363659671550869437277222354606486856186812049550589344341693403664822711470637653857431352101487484256374409178413214403186255389997719996703218968210008504670797321243942117231151859517628630349569653058698118066187391026716043545159059654577176332268476602672472482739905635999480906228670289633504973415762993972907766272134865991043814805419896534931073246213850637679606858129338795065133349542850065726766936036299370922408774380505025968168284345386665377281249588248580545930400466171993441348890777681408413792261782078132393405173617156978069157554987085001342749548897628772071501746485297338419567888447916576003827942243149921603766457101091934913083638519107992861960578751085440622105975591590796253493717379898678559428399312159501744049589763462109224611155470651431242674376807346030648379920779387984431062472207125815283005595053785608059359105377596317033846677529976095247]
c1 = 7605669437754751751610476177793759131922826980747104093542357000818497060063913924107087845360990601930555408671050799948028724299883081716937328931603327401754338192339874262419488256716174631370326490340322668255296557552788673471486135418120341918433421647466085611610623888947334038786158937441805452533779600853534965842279605411321369490368670863839480487248494416704364066973130408803943616027255257877265692956494766498575455080145534197710328071265029220229973018465376670403863050749617402496374129377281908954174277237051375359314753601975945322974975570323160950506786156943455904003195428000040276467333916553152559367716005398458970735998218533906822986614299001007314233841439480404236525261687328038543324776121839450265774921153183345047339005819754225618642933897260628741960692674491434237804555672449292585007134274881211775018630205737481800980716413758823216367911098490923039835682350013993053684506179413463125160869092176051667542368444607398819075749260134926892765114967445127938787413294708846094647437461502267474667647867530967839403461015520221145207732126447194067557777391537487237333127763013412323290051592125035563889974597343703747815163057904878702293699906325918583118298615404197934183092127
c2 = 341595253067503923027327180174884110317813506975617387801656377695966015427686992630676476188327503408928085530907804759965585203559484367772124285327044892961629152280475590498801311792956675772793138973517344692373412012812998574478644589545065453486056173491581210032155813257019845037925319344376991506868743154964217562974928300531437171616809706704371442171341158262483303393798575086111986530515621947452872485483738996766520943353286418825902780535165645491929283298305830157842776174911337005056657154851248032434586871455775785545734893373260979956976838120485456101872762991318750097419353639388326793460456278111983200869520970167760379097780850230957583925571903440260148961903310505297970989113233530838499106591857410273351285355702857494584543267209020635318257337528755084279019440848085269494771572479426796336187894016370761010594614057637109736684003912143131304981577819937788747670575676678950510781062647916588578603909110042289909263266437689901085935181226833845096239377544115217945572972017727703955324255969922780264799462917178616823113780902728249289228180706493867880051515747381052636943269639252221899055560858043281118088505415270127127991418414117681127980674701604093707405807834115516687426674435
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483


# part 1
def log(c, g, p, s):
    # given g^x = c mod p^s, 
    # solves x mod p^(s-1)
    def L(z):
        _z = pow(z,p**(s-1)*(p-1),p**(2*s + 1))
        return (_z-1)//(p**s)
    return (L(c)*pow(L(g),-1,p**(s-1))) % p**(s-1)
ks = [log(c, 69, rr, i+2) for i, c in tqdm(enumerate(ks))]


# part 2
def polygcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()
PR.<flag> = PolynomialRing(Zmod(n))
f1 = (sum(k*flag**i for i, k in enumerate(ks)) ** ((1<<7)-1)) - c1
f2 = flag ** ((1<<16)+1) - c2
print(long_to_bytes(int(-polygcd(f1, f2).coefficients()[0])))