p=165143607013706756535226162768509114446233024193609895145003307138652758365886458917899911435630452642271040480670481691733000313754732183700991227511971005378010205097929462099354944574007393761811271098947894183507596772524174007304430976545608980195888302421142266401500880413925699125132100053801973969401

q=165143607013706756535226162768509114446233024193609895145003307138652758365886458917899911435630452642271040480670481691733000313754732183700991227511971005378010205097929462099354944574007393761811271098947894183507596772524174007304430976545608980195888302421142266401500880413925699125132100053801973971467

e=65537

n=p*q

phi=(p-1)*(q-1)

c=14181751948841206148995320731138166924841307246014981115736748934451763670304308496261846056687977917728671991049712129745906089287169170294259856601300717330153987080212591008738712344004443623518040786009771108879196701679833782022875324499201475522241396314392429412747392203809125245393462952461525539673218721341853515099201642769577031724762640317081252046606564108211626446676911167979492329012381654087618979631924439276786566078856385835786995011067720124277812004808431347148593882791476391944410064371926611180496847010107167486521927340045188960373155894717498700488982910217850877130989318706580155251854

print(long_to_bytes(pow(c,inverse(e,phi),n)))

c=b'C4:\x86Q$\xb0\xd1\x1b\xa9L\x00\xad\xa3\xff\x96 hJ\x1b~\x1c\xd1y\x87A\xfe0\xe2\xfb\xc7\xb7\x7f^\xc8\x9aP\xdaX\xc6\xdf\x17l=K\x95\xd07'

iv=b'\xd1\xdf\x8f)\x08w\xde\xf9yX%\xca[\xcb\x18\x80'

key=b'\xa4\xa6M\xab{\xf6\x97\x94>hK\x9bBe]F'

aes=AES.new(key,AES.MODE_CBC,iv)

print(aes.decrypt(c))

c=199533304296625406955683944856330940256037859126142372412254741689676902594083385071807594584589647225039650850524873289407540031812171301348304158895770989218721006018956756841251888659321582420167478909768740235321161096806581684857660007735707550914742749524818990843357217489433410647994417860374972468061110200554531819987204852047401539211300639165417994955609002932104372266583569468915607415521035920169948704261625320990186754910551780290421057403512785617970138903967874651050299914974180360347163879160470918945383706463326470519550909277678697788304151342226439850677611170439191913555562326538607106089620201074331099713506536192957054173076913374098400489398228161089007898192779738439912595619813699711049380213926849110877231503068464392648816891183318112570732792516076618174144968844351282497993164926346337121313644001762196098432060141494704659769545012678386821212213326455045335220435963683095439867976162

n=335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353

m=19

x=discrete_log(mod(c,n),mod(m,n))

from tqdm import tqdm

a = 3939333498

b = 3662432446

m = 2271373817

Fp=Zmod(m)

x_=[17362, 20624]

PR.<t> = PolynomialRing(Fp)

f = a*t+b

for i in tqdm(range(2^15,2^16)):

    if(f(x_[0]*2^16+i)>>16==x_[1]):

        x = x_[0] * 2 ^ 16 + i

        PR.<x0>= PolynomialRing(Fp)

        s = f(x0) - x

        s.roots()

class LCG:

    def __init__(self):

        self.a = 3939333498

        self.b = 3662432446

        self.m = 2271373817

        self.seed = 104984523

    def next(self):

        self.seed = (self.a * self.seed + self.b) % self.m

        return self.seed >> 16

    def output(self):

        print("a = {}\nb = {}\nm = {}".format(self.a, self.b, self.m))

        print("state1 = {}".format(self.next()))

        print("state2 = {}".format(self.next()))

lcg = LCG()

lcg.output()

c=600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878

flag='Dest0g3{'

# c0 = b''.join([long_to_bytes(ord(flag[i]) ^ (lcg.next() % 10))

#               for i in range(len(flag))])

# print(c0)

c=long_to_bytes(c)

print(c)

for i in c:

    print(chr(i^(lcg.next()%10)),end='')

class RHODES_ELITE:

    def __init__(self):

        self.Doctor = 18068433704538283397

        self.Amiya = 956366446278

        self.Rosmontis = 1061992537343

        self.Blaze = 636205571590

        self.seed = 626844643882

    def next(self):

        self.seed = (self.Amiya * self.seed * self.seed + self.Rosmontis * self.seed + self.Blaze) % self.Doctor

        return self.seed >> 12

    def output(self):

        print("Amiya = ", self.Amiya)

        print("Rosmontis = ", self.Rosmontis)

        print("Blaze = ", self.Blaze)

        print("Doctor = ", self.Doctor)

elite = RHODES_ELITE()

seed=626844643882

print("Ash = ", elite.next())

print("SliverAsh = ", elite.next())

w=1920358673646340365826516899186299898354902389402251443712585240681673718967552394250439615271108958695077816395789102908554482423707690040360881719002797624203057223577713119411615697309430781610828105111854807558984242631896605944487456402584672441464316236703857236007195673926937583757881853655505218912262929700452404084

w=long_to_bytes(w)

print(w)

# W = b''.join([long_to_bytes(sha_flag[i] % (seed ** 3) ^ (elite.next() % 100)) for i in range(len(sha_flag))])

sha_flag=[]

W=[]

for i in w:

    W.append(i)

for i in range(len(W)//15):

    b=b''.join(long_to_bytes(W[j])for j in range(i*15,i*15+15))

    sha_flag.append(bytes_to_long(b)^(elite.next()%100))

print(sha_flag)

table = '-'+'}'+string.ascii_letters + string.digits

for j in sha_flag:

    print('j:',j)

    for i in tqdm(product(table, repeat=4)):

        head = ''.join(i)

        x=bytes_to_long(sha256(head.encode()).hexdigest().encode())

        if(x % (seed**3)==j):

            print(head)

            break

'''

# Dest0g3{d2a4d1af-8a80-8794-99ac-635f89494cac}

###Sage###

import binascii

# open the public key and strip the spaces so we have a decent array

pubKey =[13427720507293490146512325883268574617159432219330328705146993381673927145360640901644288, 20141580760940235219768488824902861925739148328995493057720490072510890718040961352466432, 10070790380470117609884244412451430962869574164497746528860245036255445359020480676233216, 5035395190235058804942122206225715481434787082248873264430122518127722679510240338116608, 15945418102411019548983386986381432357876825760454765337362054640737788485115761070702592, 7972709051205509774491693493190716178938412880227382668681027320368894242557880535351296, 3986354525602754887245846746595358089469206440113691334340513660184447121278940267675648, 1993177262801377443622923373297679044734603220056845667170256830092223560639470133837824, 14424309138694178868323787569917414139526733829358751538732121796720038925680375968563200, 20639875076640579580674219668227281686922799134009704474513054280033946608200828885925888, 10319937538320289790337109834113640843461399567004852237256527140016973304100414442962944, 5159968769160144895168554917056820421730699783502426118628263570008486652050207221481472, 16007704891873562594096603341796984828024782111081541764461125166678170471385744512385024, 21431572953230271443560627554167067031171823274871099587377555965013012381053513157836800, 24143506983908625868292639660352108132745343856765878498835771364180433335887397480562688, 25499473999247803080658645713444628683532104147713267954564879063764143813304339641925632, 26177457506917391686841648739990888958925484293186962682429432913555999052012810722607104, 13088728753458695843420824369995444479462742146593481341214716456777999526006405361303552, 6544364376729347921710412184997722239731371073296740670607358228388999763003202680651776, 16699902695658164107367531975767435737025117755978699040450672495868427026862242241970176, 8349951347829082053683765987883717868512558877989349520225336247934213513431121120985088, 4174975673914541026841882993941858934256279438994674760112668123967106756715560560492544, 2087487836957270513420941496970929467128139719497337380056334061983553378357780280246272, 1043743918478635256710470748485464733564069859748668690028167030991776689178890140123136, 521871959239317628355235374242732366782034929874334345014083515495888344589445070061568, 260935979619658814177617687121366183391017464937167172507041757747944172294722535030784, 13558188497103319553601134726829257708854940951798912291400514260547899231508002169159680, 20206814755845149923312893246683203471586902695229784850847250511947876761114641986224128, 23531127885216065108168772506610176352952883566945221130570618637647865525917961894756352, 25193284449901522700596712136573662793635874002802939270432302700497859908319621849022464, 12596642224950761350298356068286831396817937001401469635216151350248929954159810924511232, 6298321112475380675149178034143415698408968500700734817608075675124464977079905462255616, 16576881063531180484086914900340282466363916469680696113951031219236159633900593632772096, 21716161039059080388555783333438715850341390454170676762122508991292006962310937718030336, 10858080519529540194277891666719357925170695227085338381061254495646003481155468859015168, 5429040259764770097138945833359678962585347613542669190530627247823001740577734429507584, 2714520129882385048569472916679839481292673806771334595265313623911500870288867214753792, 1357260064941192524284736458339919740646336903385667297632656811955750435144433607376896, 678630032470596262142368229169959870323168451692833648816328405977875217572216803688448, 13767035523528788277583509997853554552321016445176745529555157584662864754146749303488512, 6883517761764394138791754998926777276160508222588372764777578792331432377073374651744256, 16869479388175687215908203382731963255239686330624515087535782777839643333897328227516416, 8434739694087843607954101691365981627619843165312257543767891388919821666948664113758208, 4217369847043921803977050845682990813809921582656128771883945694459910833474332056879104, 2108684923521960901988525422841495406904960791328064385941972847229955416737166028439552, 1054342461760980450994262711420747703452480395664032192970986423614977708368583014219776, 527171230880490225497131355710373851726240197832016096485493211807488854184291507109888, 13691306122733735259260891561123761543022552318246336753389739987577671572452786655199232, 20273373568660357776142771663830455388670708378453497081841863375462762931587034229243904, 10136686784330178888071385831915227694335354189226748540920931687731381465793517114621952, 18496063899458579590548018799226188464327109313943702975607459225539617878257399458955264, 9248031949729289795274009399613094232163554656971851487803729612769808939128699729477632, 4624015974864644897637004699806547116081777328485925743901864806384904469564349864738816, 2312007987432322448818502349903273558040888664242962871950932403192452234782174932369408, 14583724501009651370921577058220211396179876551451810141122459583270153262751728367828992, 7291862250504825685460788529110105698089938275725905070561229791635076631375864183914496, 3645931125252412842730394264555052849044969137862952535280614895817538315687932091957248, 15250686069919696567877523015546101041681916788261804972787300829582696303204606947622912, 7625343034959848283938761507773050520840958394130902486393650414791348151602303473811456, 17240392024773414288481706637155099877579911416395779948343818589069601221161792638550016, 22047916519680197290753179201846124555949387927528218679318902676208727755941537220919296, 24451678767133588791888915484191636895134126183094438044806444719778291023331409512103936, 25653559890860284542456783625364393064726495310877547727550215741563072657026345657696256, 26254500452723632417740717695950771149522679874769102568922101252455463473873813730492416, 26554970733655306355382684731243960191920772156714879989608044007901658882297547766890496, 26705205874121143324203668248890554713119818297687768699951015385624756586509414785089536, 26780323444354061808614160007713851973719341368174213055122501074486305438615348294189056, 13390161722177030904307080003856925986859670684087106527561250537243152719307674147094528, 20122801368382005598665865885197037610589267561373881968927618650295503505014477975191552, 23489121191484492945845258825867093422454066000017269689610802706821678897867879889240064, 11744560595742246472922629412933546711227033000008634844805401353410839448933939944620032, 5872280297871123236461314706466773355613516500004317422402700676705419724466969972310016, 16363860656229051764742983236501961294966190469332487416348343720026637007594125887799296, 8181930328114525882371491618250980647483095234666243708174171860013318503797062943899648, 17518685671350753087698071692394064940900979836663450559234079311680586397259172373594112, 8759342835675376543849035846197032470450489918331725279617039655840293198629586186797056, 17807391925131178418436843806367090852384677178496191344955513209594073744675433995042816, 8903695962565589209218421903183545426192338589248095672477756604797036872337716997521408, 17879568488576284751121536834860347330255601513954376541385871684072445581529499400404992, 8939784244288142375560768417430173665127800756977188270692935842036222790764749700202496, 17897612629437561334292710091983661449723332597818922840493461302692038540743015751745536, 8948806314718780667146355045991830724861666298909461420246730651346019270371507875872768, 4474403157359390333573177522995915362430833149454730710123365325673009635185753937936384, 15664922085973185313298914644766532298374848794057694060208676044510431962953517870612480, 21260181550280082803161783205651840766346856616359175735251331403929143126837399836950528, 24057811282433531548093217486094495000332860527509916572772659083638498708779340820119552, 25456626148510255920558934626315822117325862483085286991533322923493176499750311311704064, 26156033581548618106791793196426485675822363460872972200913654843420515395235796557496320, 26505737298067799199908222481481817455070613949766814805603820803384184842978539180392448, 13252868649033899599954111240740908727535306974883407402801910401692092421489269590196224, 6626434324516949799977055620370454363767653487441703701400955200846046210744634795098112, 3313217162258474899988527810185227181883826743720851850700477600423023105372317397549056, 15084329088422727596506589788361188208101345591190754630497232181885438698046799600418816, 7542164544211363798253294894180594104050672795595377315248616090942719349023399800209408, 3771082272105681899126647447090297052025336397797688657624308045471359674511699900104704, 15313261643346331096075649606813723143172100418229173033959147404409606982616490851696640, 21084351328966655694550150686675436188745482428444915222126567083878730636668886327492608, 10542175664483327847275075343337718094372741214222457611063283541939365318334443163746304, 5271087832241663923637537671668859047186370607111228805531641770969682659167221581873152, 16063264423414322108331094719103004140752617522885943107912814267158768474944251692580864, 21459352719000651200677873242820076687535740980773300259103400515253311382832766747934720, 10729676359500325600338936621410038343767870490386650129551700257626655691416383373967360, 5364838179750162800169468310705019171883935245193325064775850128813327845708191686983680, 16110139597168571546597060038621084203101399841926991237534918446080591068214736745136128, 8055069798584285773298530019310542101550699920963495618767459223040295534107368372568064, 4027534899292142886649265009655271050775349960481747809383729611520147767053684186284032, 2013767449646071443324632504827635525387674980240873904691864805760073883526842093142016, 1006883724823035721662316252413817762693837490120436952345932402880036941763421046571008, 503441862411517860831158126206908881346918745060218476172966201440018470881710523285504, 251720931205758930415579063103454440673459372530109238086483100720009235440855261642752, 125860465602879465207789531551727220336729686265054619043241550360004617720427630821376, 13490650740094929879116220649044438227327797062462856014668614156853929454220854717054976, 6745325370047464939558110324522219113663898531231428007334307078426964727110427358527488, 16800383192317222616291381045529684173991381484946042708814146920887409508915854580908032, 21827912103452101454658016406033416704155122961803350059554066842117631899818568192098304, 24341676559019540873841334086285282969236993700232003734924026802732743095269924997693440, 12170838279509770436920667043142641484618496850116001867462013401366371547634962498846720, 19513139647048375364972659404839895359468680644388329638878000082357112919178122151067648, 9756569823524187682486329702419947679734340322194164819439000041178556459589061075533824, 4878284911762093841243164851209973839867170161097082409719500020589278229794530537766912, 2439142455881046920621582425604986919933585080548541204859750010294639114897265268883456, 14647291735234013606823117096071068077126224759604599307576868386821246702809273536086016, 20751366374910496949923884431304108655722544599132628358935427575084550496765277669687296, 23803403694748738621474268098920628945020704518896642884614707169216202393743279736487936, 11901701847374369310737134049460314472510352259448321442307353584608101196871639868243968, 5950850923687184655368567024730157236255176129724160721153676792304050598435819934121984, 16403145969137082474196609395633653235287020284192409065723831777825952444578550868705280, 21629293491862031383610630581085401234802942361426533238008909270586903367649916335996928, 10814646745931015691805315290542700617401471180713266619004454635293451683824958167998464, 5407323372965507845902657645271350308700735590356633309502227317646725841912479083999232, 2703661686482753922951328822635675154350367795178316654751113658823362920956239541999616, 1351830843241376961475664411317837577175183897589158327375556829411681460478119770999808, 675915421620688480737832205658918788587591948794579163687778414705840730239059885499904, 337957710810344240368916102829459394293795974397289581843889207352920365119529942749952, 168978855405172120184458051414729697146897987198644790921944603676460182559764971374976, 84489427702586060092229025707364848573448993599322395460972301838230091279882485687488, 42244713851293030046114512853682424286724496799661197730486150919115045639941242843744, 21122356925646515023057256426841212143362248399830598865243075459557522819970621421872, 10561178462823257511528628213420606071681124199915299432621537729778761409985310710936, 5280589231411628755764314106710303035840562099957649716310768864889380704992655355468, 2640294615705814377882157053355151517920281049978824858155384432444690352496327677734, 1320147307852907188941078526677575758960140524989412429077692216222345176248163838867, 11376929106527795892898839465621865505177413571970563898745322852504166513570004716585524, 5688464553263897946449419732810932752588706785985281949372661426252083256785002358292762, 2844232276631948973224709866405466376294353392992640974686330713126041628392501179146381, 12798385171189843925916723859561259905445110198204389679873949362959076155178131224239281, 17775461618468791402262730856139156670020488600810264032467758687875593418570946246785731, 20263999842108265140435734354428105052308177802113201208764663350333852050267353758058956, 10131999921054132570217867177214052526154088901056600604382331675166926025133676879029478, 5065999960527066285108933588607026263077044450528300302191165837583463012566838439514739, 13909269013137402581858835720662039848836455726972219343626366925187786847265299854423460, 6954634506568701290929417860331019924418227863486109671813183462593893423632649927211730, 3477317253284350645464708930165509962209113931743054835906591731296946711816324963605865, 13114927659516044762036723391441281698402490467579596610484079872044528696890043116469023, 17933732862631891820322730622079167566499178735497867497772823942418319689426902192900602, 8966866431315945910161365311039583783249589367748933748886411971209159844713451096450301, 15859702248531842394385051581878318608922728185582536066973989992000635263338606182891241, 19306120157139790636496894717297686021759297594499337226017779002396372972651183726111711, 21029329111443764757552816285007369728177582298957737805539673507594241827307472497721946, 10514664555721882378776408142503684864088791149478868902769836753797120913653736248860973, 16633601310734810628692572997610369149342329076447503643915702383294615797808748759096577, 19693069688241274753650655425163711291969098039931821014488635198043363239886255014214379, 21222803876994506816129696638940382363282482521673979699775101605417736960925008141773280, 10611401938497253408064848319470191181641241260836989849887550802708868480462504070886640, 5305700969248626704032424159735095590820620630418494924943775401354434240231252035443320, 2652850484624313352016212079867547795410310315209247462471887700677217120115626017721660, 1326425242312156676008106039933773897705155157604623731235943850338608560057813008860830, 663212621156078338004053019966886948852577578802311865617971925169304280028906504430415, 11707875343451908608306395436341970191724222291109225125339769968980707480996333886881298, 5853937671725954304153197718170985095862111145554612562669884984490353740498166943440649, 14303237868736846591380967785444019265228989074485375473865726498641232211230964106386415, 18527887967242292734994852819080536349912428038950756929463647255716671446597362687859298, 9263943983621146367497426409540268174956214019475378464731823627858335723298681343929649, 16008241024684442623053082131128660804776040511445758424896695820325223202631221306630915, 19380389545216090750830909991922857119685953757430948404979131916558666942297491287981548, 9690194772608045375415454995961428559842976878715474202489565958279333471148745643990774, 4845097386304022687707727497980714279921488439357737101244782979139666735574372821995387, 13798817726025880783158232675348883857258677721386937743153175495965888708769067045663784, 6899408863012940391579116337674441928629338860693468871576587747982944354384533522831892, 3449704431506470195789558168837220964314669430346734435788293873991472177192266761415946, 1724852215753235097894779084418610482157334715173367217894146936995736088596133380707973, 12238695140750486988251758468567831958376600859294752801477857474893923385279947325020077, 17495616603249112933430248160642442696486233931355445593269712743843017033621854297176129, 20124077334498425906019493006679748065541050467385791989165640378317563857792807783254155, 21438307700123082392314115429698400750068458735400965187113604195554837269878284526293168, 10719153850061541196157057714849200375034229367700482593556802097777418634939142263146584, 5359576925030770598078528857424600187517114683850241296778401048888709317469571131573292, 2679788462515385299039264428712300093758557341925120648389200524444354658734785565786646, 1339894231257692649519632214356150046879278670962560324194600262222177329367392782893323, 12046216148502715764064185033536601740737572837189349354628084137507144005665577026112752, 6023108074251357882032092516768300870368786418594674677314042068753572002832788513056376, 3011554037125678941016046258384150435184393209297337338657021034376786001416394256528188, 1505777018562839470508023129192075217592196604648668669328510517188393000708197128264094, 752888509281419735254011564596037608796098302324334334664255258594196500354098564132047, 11752713287514579306931374708656545521695982652870236359862911635693153591158929916732114, 5876356643757289653465687354328272760847991326435118179931455817846576795579464958366057, 14314447354752514266037212603522663097721929164925628282496511915319343738771613113849119, 18533492710250126572322975228119858266158898084170883333779039964055727210367687191590650, 9266746355125063286161487614059929133079449042085441666889519982027863605183843595795325, 16009642210436401082385112733388491283837658022750790025975543997409987143573802432563753, 19381090138092069980496925293052772359216762513083464205518556005101048912768781850947967, 21066814101919904429552831572884912896906314758249801295290062008946579797366271560140074, 10533407050959952214776415786442456448453157379124900647645031004473289898683135780070037, 16642972558353845546692576819579754941524512191270519516353299508632700290323448524701109, 19697755312050792212650657336148404188060189597343328950707433760712405486143604897016645, 21225146688899265545629697594432728811328028300379733667884500886752258084053683083174413, 21988842377323502212119217723574891122961947651897936026473034449772184383008722176253297, 22370690221535620545363977788145972278778907327657037205767301231282147532486241722792739, 22561614143641679711986357820431512856687387165536587795414434622037129107225001496062460, 11280807071820839855993178910215756428343693582768293897707217311018564553612500748031230, 5640403535910419927996589455107878214171846791384146948853608655509282276806250374015615, 14196470800829079403302663653912465824383856897400142666957588334150696479385005821673898, 7098235400414539701651331826956232912191928448700071333478794167075348239692502910836949, 14925386733081139290130034839836643173393897726058104859270181089933729460828132090084565, 18838962399414439084369386346276848303994882364737121622165874551362920071395946679708373, 20795750232581088981489062099496950869295374684076630003613721282077515376679853974520277, 21774144149164413930048899976107002151945620843746384194337644647434813029321807621926229, 22263341107456076404328818914412027793270743923581261289699606330113461855642784445629205, 22507939586601907641468778383564540613933305463498699837380587171452786268803272857480693, 22630238826174823260038758118140797024264586233457419111221077592122448475383517063406437, 22691388445961281069323747985428925229430226618436778748141322802457279578673639166369309, 22721963255854509973966242919072989332013046810926458566601445407624695130318700217850745, 22737250660801124426287490385895021383304456907171298475831506710208402906141230743591463, 22744894363274431652448114119306037408950161955293718430446537361500256794052496006461822, 11372447181637215826224057059653018704475080977646859215223268680750128397026248003230911, 17062492623692477352416397456185036069535473990531498800142418346771119539495004636281546, 8531246311846238676208198728092518034767736995265749400071209173385559769747502318140773, 15641892188796988777408468290404785734681801999340943892566388593088835225855631793736477, 19197215127272363828008603071560919584638834501378541138813978302940472953909696531534329, 20974876596510051353308670462138986509617350752397339761937773157866291817936728900433255, 21863707331128895115958704157428019972106608877906739073499670585329201249950245084882718, 10931853665564447557979352078714009986053304438953369536749835292664600624975122542441359, 16842195865656093218294044965715531710324585721184753960905701652728355653469441905886770, 8421097932828046609147022482857765855162292860592376980452850826364177826734720952943385, 15586817999287892743877880167787409644879079932004257682757209419578144254349241111137783, 19169678032517815811243309010252231539737473467710198033909388716185127468156501190234982, 9584839016258907905621654505126115769868736733855099016954694358092563734078250595117491, 16168688541003323392115196178921584602232301868635618701008131185442337208021005932224836, 8084344270501661696057598089460792301116150934317809350504065592721168604010502966112418, 4042172135250830848028799044730396150558075467158904675252032796360584302005251483056209, 13397355100499284863318768448723724792576971235287521530156800404576347491984506376194195, 18074946583123511870963753150720389113586419119351829957609184208684229086974133822763188, 9037473291561755935481876575360194556793209559675914978804592104342114543487066911381594, 4518736645780877967740938287680097278396604779837957489402296052171057271743533455690797, 13635637355764308423174838070198575356496235891627047937231932032481583976853647362511489, 18194087710756023650891787961457814395546051447521593161146750022636847329408704315921835, 20473312888251881264750262907087433915070959225468865773104159017714479005686232792627008, 10236656444125940632375131453543716957535479612734432886552079508857239502843116396313504, 5118328222062970316187565726771858478767739806367216443276039754428619751421558198156752, 2559164111031485158093782863385929239383869903183608221638019877214309875710779099078376, 1279582055515742579046891431692964619691934951591804110819009938607154937855389549539188, 639791027757871289523445715846482309845967475795902055409504969303577468927694774769594, 319895513878935644761722857923241154922983737897951027704752484651788734463847387384797, 11536216789813337261685230355320147294759425370657044706383160248721949708213804328358489, 17144377427780538070146984104018600364677646187036591545722364130757030195088782798845335, 19948457746764138474377860978367826899636756595226364965391966071774570438526272034088758, 9974228873382069237188930489183913449818378297613182482695983035887285219263136017044379, 16363383469564904057898834170950483442207122650514660433878775524339697950613448643188280, 8181691734782452028949417085475241721103561325257330216939387762169848975306724321594140, 4090845867391226014474708542737620860551780662628665108469693881084924487653362160797070, 2045422933695613007237354271368810430275890331314332554234846940542462243826681080398535, 12398980499721675942923046062042931932435878667365235469648207476667286462895221174865358, 6199490249860837971461523031021465966217939333682617734824103738333643231447610587432679, 14476014157804288425035130441869259700406903168549378059942835875562876956705685928382430, 7238007078902144212517565220934629850203451584274689029971417937781438478352842964191215, 14995272572324941545563151536825841642399659293845413707516492975286774580158302116761698, 7497636286162470772781575768412920821199829646922706853758246487643387290079151058380849, 15125087175955104825695156810564987127897848325169422619409907250217748986021456163856515, 18938812620851421852151947331641020281246857664292780502235737631504929833992608716594348, 9469406310425710926075973665820510140623428832146390251117868815752464916996304358297174, 4734703155212855463037986832910255070311714416073195125558934407876232458498152179148587, 13743620610480297170823362342813654252453790709744666755310251210334171570230956724240384, 6871810305240148585411681171406827126226895354872333377655125605167085785115478362120192, 3435905152620074292705840585703413563113447677436166688827562802583542892557739181060096, 1717952576310037146352920292851706781556723838718083344413781401291771446278869590530048, 858976288155018573176460146425853390778361919359041672206890700645885723139434795265024, 429488144077509286588230073212926695389180959679520836103445350322942861569717397632512, 214744072038754643294115036606463347694590479839760418051722675161471430784858698816256, 107372036019377321647057518303231673847295239919880209025861337580735715392429349408128, 53686018009688660823528759151615836923647619959940104512930668790367857696214674704064, 26843009004844330411764379575807918461823809979970052256465334395183928848107337352032, 13421504502422165205882189787903959230911904989985026128232667197591964424053668676016, 6710752251211082602941094893951979615455952494992513064116333598795982212026834338008, 3355376125605541301470547446975989807727976247496256532058166799397991106013417169004, 1677688062802770650735273723487994903863988123748128266029083399698995553006708584502, 838844031401385325367636861743997451931994061874064133014541699849497776503354292251]

nbit = len(pubKey)

encoded = 1475864207352419823225329328555476398971654057144688193866218781853021651529290611526242518

print("start")

# create a large matrix of 0's (dimensions are public key length +1)

A = Matrix(ZZ, nbit + 1, nbit + 1)

# fill in the identity matrix

for i in range(nbit):

    A[i, i] = 1

# replace the bottom row with your public key

for i in range(nbit):

    A[i, nbit] = pubKey[i]

# last element is the encoded message

A[nbit, nbit] = -int(encoded)

res = A.LLL()

for i in range(0, nbit + 1):

    # print solution

    M = res.row(i).list()

    flag = True

    for m in M:

        if m != 0 and m != 1:

            flag = False

            break

    if flag:

        print(i, M)

        M = ''.join(str(j) for j in M)

        # remove the last bit

        M = M[:-1]

        M = hex(int(M, 2))[2:]

        print(bytes.fromhex(M))