reconstruct modulus by lattice

题目给出了一组方程，形式为：

$e^{m_i} \equiv c_i(\bmod n)$

然而$m_i$很大，无法通过求$gcd$来获得$n$。
由于方程的组数足够多，如果将所有方程联系起来可有效减小指数。

格子的构造如下：

$\left( \begin{matrix} m_1 & 1 & \\ m_2 & & 1 \\ \vdots & & & \ddots\\ m_n & \cdots &\cdots &\cdots &1 \end{matrix} \right)$

LLL算法后的得到的格子，以第一行为例，可表示为：

$(k_1*m_1+k_2*m_2+\cdots + k_n*m_n, k_1 , k_2 , \cdots,k_n)$

也即$$e^{\sum_1^nk_i*m_i}\equiv \prod_1^n c_i^{k_i} (mod;n)$$

如果$\sum_1^nk_i*m_i$为负就让其乘到右边；如果$k_i$为负，就让其乘到左边，最后将得到的数一直求$gcd$即可。

(测试时gcd求出来的结果需要再次因子分解，存在2、3、5等小因子，本题的数据很特殊，没有恢复出n)

from Crypto.Util.number import *
from math import prod
from secret import flag

def keygen(pbits,kbits,k):
    p = getPrime(pbits)
    x = [getPrime(kbits + 1) for i in range(k)]
    y = prod(x)
    while 1:
        r = getPrime(pbits - kbits * k)
        q = 2 * y * r + 1
        if isPrime(q):
            return p*q, (p, q, r, x)

def encrypt(key, message):
    return pow(0x10001, message, key)

key = keygen(512, 24, 20)
flag = bytes_to_long(flag)
messages = [getPrime(flag.bit_length()) for i in range(47)] + [flag]
enc = [encrypt(key[0], message) for message in messages]

print(messages[:-1])
print(enc)

"""
[12663746096003602034805550137868194720916906489657622295298194239094517182776571415625767646380772563193, 14132419026281300247821055412800131398930894216489258113904728404581538907301679419214447815004356250213, 11655428754671560771921463003911904370642761461141746853172776137663446218950185460123311583744244576651, 14437678697063990859655299315506460156072449476596814455497580042773427427201191616010438921219697566207, 15002874749915800226497487675982756978120590555038984559176137265082604998701016560366851521550375289619, 12200429000300054982769822088303708088147776935798495143123101000414999518256814919436691701219929977443, 12022028158932066252554600210953428074479648616693562203622365444081153755664547825203072727322619340391, 15326141484175696149121655412465633104078151316690977231668152920998359592830509503478074055112999574981, 14056771497651385035371546931678946327225541945352605439360765820739927703122904981469057904317776921263, 13627527116278874003582695444496282221231787451158428826309766728816516675463929802270425585235619637873, 9532386535492144267147831028913273489858437724880203373826043347568852523770420241749859385487406483979, 12105119318974808780726286054732236125970820406031457561069902254615102811695780762128818161404504498571, 17375473832716984207301483561766127121416492000960248004847175097439386482194277684885433842142485766979, 16554810021656773269015172383701694656984382699786774223957939352351900556944802452753429128313990996737, 15176915452575891079550629883578986339427556051613114385723386598491455091420380698285277882392147506173, 11806010168620746459109864194771894332952141161819393026586030536903429301218820465075218508304178337693, 10301071899683854933212873261118138833852167112586044571755364655196343466043810121544973678672008613803, 14166775554072964505385268662634177869100699819638306431597407356342551153097479752104518536035399939371, 10149638549982466694759374439977996929610044260455135782295224680189567726832086180314113209468279041757, 11781584892220250690574681563680940126762935519793655192784959502937368059247206358504250608454259891727, 15038928305561471041226064029963106243541545002574865065995806409790534237748546487849249858106550078231, 9580888622178339972260574652417101092469152244093773478970996513098265707736420799213172454323127622633, 16832519731577306391043658360018784702605792203422700389327004686532539689734917760321648488230888187721, 10867599307636425749899548870300113988038540052791923844000360343405148990662095113016671010590469235521, 17467115681041482108467932296242227024623105030257775065640719199713712198126072518920191142637850906683, 9273417146144052655615407700694821772909515142773572691972830367235325718875094311189518007289192669189, 16632824238934881411171218388021828930721084481281881679074243665187528749774173422168476107286651950721, 10581883242475329842566787060887333718055756499659396478793112531016759279124005692583324120011287554937, 17915505401279990026021751220853729828697276123216111805478995734037531915469950842915053859630212282669, 10782951127933994337893639031146049444366465583233074369169440143266558605440864932670063972448118770053, 10176756020954218340342729294765357250100532131670575581012530671423202386081022361061175199978931328671, 13658827352593547554221598195357688731028052333550989106789568768190119263114463407419978955533304562429, 14891712870731238492263819443444939062051933851768953568786715305574300162320426370160524102148144647341, 10385921231223717361217489427301590556224642053715247311910689044243066369482114225234839934781933387317, 17013409655721508165863397312465280020898749311014596585552718375774263478496723317784119730976514130473, 16986882920113484087693092000585103501548559643718025617656633308381676660630862412036186585506899774161, 11453352651216365241578914867406398737971509207465133323955060019598413539108767754962077278598322864301, 16755633786275870614857653299503803951700995626343095443892626619957330702430787078783721161855813805163, 15448657521962024971112157922187306191950692633208198318716657601508105720490330518613598428258399393999, 13445442344820784802664041567908665004819931321301423637095302391845536651285135635627140656111561505441, 9557468167801329362767525412300043569009743279963873824012642650395198714316574006341471079208144585967, 17098254197749431716632768896312100035386578636133269314483367740073947526081776782262947168490582199483, 16835407022333577513897329377457949073175792779993839585759661291470395273625057511614988721879320902427, 16306999806399827080235326712427101893348438406069647763492946439224757958791811990717080643111227201807, 13580334016425716627812690149777819923090303265405445549999854984914558569659989887973025065946663385157, 13110792710299272609698528958861611699151645629852258616789302701448426819110564884922775851490202636881, 14165423701777249263816463401081760426834162610596319073642833757104030978264487767967134870804656476289]
[57232608914198175109785709371300232177693855726597984936053900368555183181147336312895836187534080073427080654999615527778639368550840082346447311859780241331567239734555580467938250447225626069106101196513103259622377455430858622976701082331136388721125159472447812785142939993215201079156381454179231774978621, 119018622019252168934355440063416070353601068126795157593996773179308331829090813617846715074323709342886276077497762149186679801528162789221386514455479512683730420488200545921618210431980938300089161291644469992260008163539403051482736189309308446661006179700799915857633850683598284957540073230007864001007687, 6122163628062914171517341768803876718204225239795039176674815707292832652022824779820529176787981304153138541719456878186186204622264727458463951667567490266297270999694085051562030232607306260099357571419311953711317201937945632812425299150895404339807975311146159116266980933520593480837401136212447204108049, 28540414123410824174116871648980258694595184814510554181081596920388496284279412323405941240185964737191832645783356008854524037236288389256214745517114972018198837498973693612698538462787963569692770376251970527324079472545283749882989761108810944657299270896094407238648710873736756511689128494479553996569980, 67278930120416218881331446326848251697009804802460482086707926724916142606112769752677376855224039704540779071775615502924601665778596652537347982371095563171698757196325528893745482251006926923517931248138004165768769736874237648555305584043598268309988084995366843540992183241120300859132869831366331600710558, 100441125745454072827180775943684938314832119776801393398707172733554934663150253857204265229489246969289062535749135436558322252067664012937043065312761808726865341867434868750714642040389825289571661397788319344833736025265091503110460610697145217047563412817555970653508368515813966481892006317185835016451596, 15216117530042455399400804489826720273427315418739000010460816009280452996314747501422962977476242525449009860773153042079850388424528150860792687843182357662143003598943761328772890589193531750128029534007416927554961470396996998968754712117453852091512966620492890336420903174876176537738798246079795219745854, 118541309065015685856335846391033886567572688280488418106011358526392112399337378946425518000792132290816624302062971705513928029491812938656625783759873895027943910919262567277145905349608195128462056469713961540517667447151625332802836450303814775982440575824290593573150355925407077920563410787306702533205463, 128389881064636709419836763141515677495188380000146888480597348696945592678282670905925791343389121784046644286523689339199763106802825872989267651350937875209973619149021581029505933792860832895657339679214599201637317323656626462814144544301491824556559035411714532843566344523217819358896371943350639942459949, 34093856775781856551191147692508868666336509269856011110737357636215480841525445733330940087981829545127700802659540443440189524089943638275810382531930541835422545115011751274985231327701498777770819771076207589931619915169066258894847224146756480054695482898013102816123551733159333649898586559428557971850701, 81300851339401181812622971818456807765918449363627764350395250541212488081576716833807248879650649362171107666776341430534661723935291947760015791546044469452363961895420142561758463985262985214902182739623920284210707167192767526178841138011634179210631980347705048905526562571093675029106563005606342950051013, 81184744346790924098390626343061862533926196813436264423392782313183788824888005366960636464932666991679250036623225102844077245305279615789985297028151686367395487188181416047313913708495129221758772076767595640173439548175714389499004700598291317543926421962858976817846596643104360539905688568401039734718483, 26434131154005660208202418251350553299645786233494766029878297162082886997824532111995385786035751557354362898428335530451272701789617149071688592843246870280783453272275136306294400300985731992703683476375688305074195262278872080404088938102904111143101067942664642550110639626664123760598968951181617689902541, 20583461169361164936012239952506086042941935876382559469522600586017850800344765779998955301922686194592613728117977392668857817500652927316170071259763189098650100319355732975236340932783385931830714959967369110831948835561327035695862957210809046317597465402541788054523440985447601668375174517972307420752222, 99534127272271736561819944763606095922497555550678291381059549633615143166598789208945263137876687923783077645427746546609553288013773320686523582406074630183160062915395771686193917033832627369751874816677354435908597099043633357467600006811423136496389263128632570405208493745830930161893550082268510553243436, 118512116206510628620173620535467344051381976286214661348788449888449951031872461765117206926632677694087945546315408145619615151832782942014233116281935093137585570386446879683134361566600024471557481076162998555307020705103001626351022137545564104344410566269738892608918426693130348185415804993793721209609921, 39696874135154683267112097021680040753243138159093000082671302585498437603319904894403312138376713524983452218540365741436497014252623022059517764732201708697832675412789710043016297658647765241931376357562085304351217443979514385699767267553378445677211510486519988739144271419362000197607483106320082211157894, 25615713579794183863442485192387430658723428296464586587898591117935830443598276803565696400498331135396182162761634590925312795732761646132215168836455602406883764926399157309533193399134550418083687077959980816090474500772169035534758695041065067455682003512957204985608587710672977761801979298600719822016047, 23793209649566114665504267496369174053459786578228840738712746160813356913085291840670926485938467021921249748937163453045493268190727694834746331675450612307162991196358494672951680343821853030212625697896822806418811182729559057694617576595345840050914186351202035936407830993232414495830287089643357113630503, 84900868031750701719170495739268701340448411132522906627713496129145064055990332922002486194735907569742410314242506161002441004555229668928980128799296166340146123428623689620142768423244946548591211248837198305592226407665478362906541272913507633212921149441249303673799120352922183629944134036918567534983647, 64854743778344461573875505197765202610602120089852481429093133918839065327096609472074901493597943717665732351345476707313576146260579823636441977310462506242356225915419035285099759708938797787590056266006186272630085683224747473152107252181715962546230577202193544842264175396407294764016400072051626879823666, 43786460809814877850055135457752884384516501548292829314979687937607951889102449353983106504856286698338120117264846883578454109760559338097644845777254246143813247771973297517920813642987087609503855062297041188130113307877018724419913492364040334823999299826485220355118533227105208525871102164850743592197880, 18410848816279000082865665087967308434683881846057587302207644885782121929540614117218622845465184222863920784374706231486900135399669880462420214078693028046048021435260904923927365018413834214333078986702654848677487103752777924965608975606985449643730404332158705821979821026927627232457593514769409557857794, 37528795642427381026743303290555251064602380591515328584173853460474597557188114837322912676348557014234144738972886931444325218088188023630647534035725264163124845482521689580289083806870704489342225504049591490404844227836527733261384542641712205218746355586140270679557466938414940696629906671790333847339100, 120184174837129922978041761049752494349805405363915733328766090037154677842877770589616516870003359227784292556831725911705007653205940334469000068369577478846709121385821095258347556939153698007282502763909940256677799743506174272974157274102970394457871359832172736455842603413137518696350897940124898715264328, 85114042547376870094991062686681561109370712951526036710890642223255504371925133357863720777505794177722019923294054968209724320983289575941774562335331869126256931667309246608290713579479837728662330515334593645923196813941733211556279847804080648269475904763815679632829504041349748084243435407170116086099571, 85664036841997000249918266611625095874187200068219663599240259437252325179648759068399867768105884800411762830251668911635511387529518068874630535460984056737847815294298413093595113435496939074803361947656093885514112089591812880957906107416384430811199239381641849560512236254320481734660943314397466382518670, 19868151443713684033326315419488805314642951421071058037081518185917142386124119384204580739191353408815653188976676798334838959292276152979270636624021744528913109029922119160800340250667168104047373320086805282333539262671835560171422052545510197952709359772287020357635465074316209873689272267323257955153323, 51029267901687836725907965568430647221250571180244643611425953900542586039831128405596005089082767047574164924899010105416329727934881100139413736187064637473224707121868210639131044204973756282046850557215004436827715093816988545799405346151923231447395532258095016482637754870243670358652069698049268883589124, 88034211107477606037608516993038006849109216205386189419249337698181850592850024345069840216575652166713813867810010665618768531718281563277119288198903566342692567184172362056718934854721638856943432002177665039289279569277329521972446746782839371702287518786028884532536089431813622499739059673650919651503327, 34290724215292206898895850910853573969604203610446796482457188079779084234166755672139575160998526644200788650835348904310076192206731369137747137479474593487141698098918402805229456473832106349331555085747621113162720499571078980178142378770306917802125052880993548469701984751330079122660792309621426541588076, 90927188279218437043454554956642015346713372562371359261616779706538939681408456355974513604735454447880695728673117860551338566945192506092751947158505621256166944871575026077958544804376039892815849827345907923264667687859857788352006910436664478067757651891635634923727530789609690792776873591562573033390634, 53732343203006760442398433872134781295830656980276609591138146207626163562517843649120913243776843334107106691749493938619111007479062412456809500791493383632196471953312152159801577623906430605844235078132185853920208052494745920119335711435221738446984963476234515199656235009292715443135922168345909287531773, 49031927534145883184926164295828977811711469424781078012610739070444671584077746477613031478660697183975633421868019649807499312667206591889141783516733744766298933391910692474266962004086039942805103040216748384407579306341588913664371259037264104088526364892368819697446167356277559716864693012958967681100260, 30963093465814372302516642776466055177417508152527408097213764844911320991146439597064292750638894222728431395063768524250417428928630674742251008274743494898189847494654965058948152674638339661926080272873883532044920176841760857878305035802233007949695617087173051988751329551256926898662442540254844991028514, 38910112932907768300302033715233195117875021511365865825041254667079681402773472898691511153844674335901286966993706447991762641623427579348204449246293604501210799161052618900641298875451688446687090763591699182741091728011538059864656433159402170621985800117954635372431554313743158156450491482836596392698540, 38443585562211316355274911393358256761473644112925764889560030180611756915515144544478860742103854890487528907562890898220560352513541741776265949250582845223992532020273016857208957223972389401808992966177007678770950599391794859006751879990019132124290539952279226068978275232584696063868776228658398019508687, 68550545600754879458876198377420845829320975904563551687242682944061564106671329644108261571744526116101799247679080797784186089149212343674697695440503566377158992929812917026042984952900100484829086299001655020193931835567043420882168129444729139288226492289343177679790267321958684637995637195757642488407276, 14035877123755570541439737876187097058990065301274722507585166336666626066786310262014548146436251719506889507596006387639929786023894491544460425397241776709067116382427351107782288254085502357976399257409284873091313992760783124271797334837519629008018411961593376262210281164953819570277107742944093278192891, 84973935660270819758814233083142240710785309884502607538970282884173754299778363893310221726403783947387743415857505995412132704938765096035328014089802283590788326117498458965239857137170690424984064818395940808347999385981549657227261498421032954560304304123396784276562818279812166711176719165057986653655269, 127652767021260495264466818414737386226807627335092643140999814315165072776677100093295944121947491864703175075802550400479697578962892452948470076586765670039963843210663006398013035858021917292520141025024089841431675871893235220229330118710120234682740731230605781585933497507868222142730438320650171223860410, 10820660907713821060756049660148560389325280624093461093810612541407581846537858936018021071684134263919140572079037344255372562710590250975822332043248751602294057721687638216684660439386848864418110118512208174355768432871226086246312894904364514743506427898091247247420131030953043354451982106624371303476576, 22509117536200148044923857446175408893075911404191032333097026503103010276105955757884180889706600230561199133331513880035633926105853975206764813984995520499767942092693844323122983122419315389669151529120786805203317761028263320034762418835415040762546573582987418970210522622738218431543314964785802667587831, 17110527541362531877473330877601602495160188646106725957393956572731745660242627602027036247078158084197564066866793058830963123952529593790431750896935886096261794752083336388036458068396262377010283577634659205378999555399253008352426584270580993143755095742288863170042056511437561276980640231653447089696471, 61348969566002296992170896072625129282323865986171588065667375012252011568769255349045185267959292869829157950934447113661709763529293480980845035985257633760151897807384916925942496992692306256026272824777993338140456567783548738678972934778493803536774329693410845609652017903413643751788619405927638767324811, 22510200266842330474614868643482821984644884364293177816481436665684674092037143647321900145327127043489514908412852947132346581389833878070779594530084319995806315545603004624097888294152486960640012202384261073555560735843725251439470919050946837207965392746584707716070872006144735413123120629275998839207636, 50720056568644721066647792700132746371519628076501379437908002312608804539261649596142852235153482308383208999791237037363767518135800305446886547979409480500284980037243584682485311702605225147297356529617446995741990013066746514569978566927909505486404585512297997162119969692237951781374377056093090642010097, 91561944814950778736488535643520052714900101756544637483800925876319855838327993556442983654484996766433049736153189800056457912285338408230393372558184963346036063617106521919740962726456954911219888157214487326900658606650604294547947205051640436119495039170478782141363198165616660075024383933961325219072058]

"""

exp为：

from Crypto.Util.number import *

def compute_n(row):
    if row[0] > 0:
        right = 1
        left = pow(e, row[0])
    else:
        right = pow(e, -row[0])
        left = 1
    for i, coff in enumerate(row[1:]):
        if coff > 0:
            right *= enc[i]^coff
        else:
            left *= enc[i]^(-coff)
    return left - right
        
e = 0x10001
p = getPrime(512)
q = getPrime(512)
n = p * q
msg = [getPrime(400) for i in range(47)]
enc = [ZZ(pow(e, message, n)) for message in msg]

# msg = [12663746096003602034805550137868194720916906489657622295298194239094517182776571415625767646380772563193, 14132419026281300247821055412800131398930894216489258113904728404581538907301679419214447815004356250213, 11655428754671560771921463003911904370642761461141746853172776137663446218950185460123311583744244576651, 14437678697063990859655299315506460156072449476596814455497580042773427427201191616010438921219697566207, 15002874749915800226497487675982756978120590555038984559176137265082604998701016560366851521550375289619, 12200429000300054982769822088303708088147776935798495143123101000414999518256814919436691701219929977443, 12022028158932066252554600210953428074479648616693562203622365444081153755664547825203072727322619340391, 15326141484175696149121655412465633104078151316690977231668152920998359592830509503478074055112999574981, 14056771497651385035371546931678946327225541945352605439360765820739927703122904981469057904317776921263, 13627527116278874003582695444496282221231787451158428826309766728816516675463929802270425585235619637873, 9532386535492144267147831028913273489858437724880203373826043347568852523770420241749859385487406483979, 12105119318974808780726286054732236125970820406031457561069902254615102811695780762128818161404504498571, 17375473832716984207301483561766127121416492000960248004847175097439386482194277684885433842142485766979, 16554810021656773269015172383701694656984382699786774223957939352351900556944802452753429128313990996737, 15176915452575891079550629883578986339427556051613114385723386598491455091420380698285277882392147506173, 11806010168620746459109864194771894332952141161819393026586030536903429301218820465075218508304178337693, 10301071899683854933212873261118138833852167112586044571755364655196343466043810121544973678672008613803, 14166775554072964505385268662634177869100699819638306431597407356342551153097479752104518536035399939371, 10149638549982466694759374439977996929610044260455135782295224680189567726832086180314113209468279041757, 11781584892220250690574681563680940126762935519793655192784959502937368059247206358504250608454259891727, 15038928305561471041226064029963106243541545002574865065995806409790534237748546487849249858106550078231, 9580888622178339972260574652417101092469152244093773478970996513098265707736420799213172454323127622633, 16832519731577306391043658360018784702605792203422700389327004686532539689734917760321648488230888187721, 10867599307636425749899548870300113988038540052791923844000360343405148990662095113016671010590469235521, 17467115681041482108467932296242227024623105030257775065640719199713712198126072518920191142637850906683, 9273417146144052655615407700694821772909515142773572691972830367235325718875094311189518007289192669189, 16632824238934881411171218388021828930721084481281881679074243665187528749774173422168476107286651950721, 10581883242475329842566787060887333718055756499659396478793112531016759279124005692583324120011287554937, 17915505401279990026021751220853729828697276123216111805478995734037531915469950842915053859630212282669, 10782951127933994337893639031146049444366465583233074369169440143266558605440864932670063972448118770053, 10176756020954218340342729294765357250100532131670575581012530671423202386081022361061175199978931328671, 13658827352593547554221598195357688731028052333550989106789568768190119263114463407419978955533304562429, 14891712870731238492263819443444939062051933851768953568786715305574300162320426370160524102148144647341, 10385921231223717361217489427301590556224642053715247311910689044243066369482114225234839934781933387317, 17013409655721508165863397312465280020898749311014596585552718375774263478496723317784119730976514130473, 16986882920113484087693092000585103501548559643718025617656633308381676660630862412036186585506899774161, 11453352651216365241578914867406398737971509207465133323955060019598413539108767754962077278598322864301, 16755633786275870614857653299503803951700995626343095443892626619957330702430787078783721161855813805163, 15448657521962024971112157922187306191950692633208198318716657601508105720490330518613598428258399393999, 13445442344820784802664041567908665004819931321301423637095302391845536651285135635627140656111561505441, 9557468167801329362767525412300043569009743279963873824012642650395198714316574006341471079208144585967, 17098254197749431716632768896312100035386578636133269314483367740073947526081776782262947168490582199483, 16835407022333577513897329377457949073175792779993839585759661291470395273625057511614988721879320902427, 16306999806399827080235326712427101893348438406069647763492946439224757958791811990717080643111227201807, 13580334016425716627812690149777819923090303265405445549999854984914558569659989887973025065946663385157, 13110792710299272609698528958861611699151645629852258616789302701448426819110564884922775851490202636881, 14165423701777249263816463401081760426834162610596319073642833757104030978264487767967134870804656476289]
# enc = [57232608914198175109785709371300232177693855726597984936053900368555183181147336312895836187534080073427080654999615527778639368550840082346447311859780241331567239734555580467938250447225626069106101196513103259622377455430858622976701082331136388721125159472447812785142939993215201079156381454179231774978621, 119018622019252168934355440063416070353601068126795157593996773179308331829090813617846715074323709342886276077497762149186679801528162789221386514455479512683730420488200545921618210431980938300089161291644469992260008163539403051482736189309308446661006179700799915857633850683598284957540073230007864001007687, 6122163628062914171517341768803876718204225239795039176674815707292832652022824779820529176787981304153138541719456878186186204622264727458463951667567490266297270999694085051562030232607306260099357571419311953711317201937945632812425299150895404339807975311146159116266980933520593480837401136212447204108049, 28540414123410824174116871648980258694595184814510554181081596920388496284279412323405941240185964737191832645783356008854524037236288389256214745517114972018198837498973693612698538462787963569692770376251970527324079472545283749882989761108810944657299270896094407238648710873736756511689128494479553996569980, 67278930120416218881331446326848251697009804802460482086707926724916142606112769752677376855224039704540779071775615502924601665778596652537347982371095563171698757196325528893745482251006926923517931248138004165768769736874237648555305584043598268309988084995366843540992183241120300859132869831366331600710558, 100441125745454072827180775943684938314832119776801393398707172733554934663150253857204265229489246969289062535749135436558322252067664012937043065312761808726865341867434868750714642040389825289571661397788319344833736025265091503110460610697145217047563412817555970653508368515813966481892006317185835016451596, 15216117530042455399400804489826720273427315418739000010460816009280452996314747501422962977476242525449009860773153042079850388424528150860792687843182357662143003598943761328772890589193531750128029534007416927554961470396996998968754712117453852091512966620492890336420903174876176537738798246079795219745854, 118541309065015685856335846391033886567572688280488418106011358526392112399337378946425518000792132290816624302062971705513928029491812938656625783759873895027943910919262567277145905349608195128462056469713961540517667447151625332802836450303814775982440575824290593573150355925407077920563410787306702533205463, 128389881064636709419836763141515677495188380000146888480597348696945592678282670905925791343389121784046644286523689339199763106802825872989267651350937875209973619149021581029505933792860832895657339679214599201637317323656626462814144544301491824556559035411714532843566344523217819358896371943350639942459949, 34093856775781856551191147692508868666336509269856011110737357636215480841525445733330940087981829545127700802659540443440189524089943638275810382531930541835422545115011751274985231327701498777770819771076207589931619915169066258894847224146756480054695482898013102816123551733159333649898586559428557971850701, 81300851339401181812622971818456807765918449363627764350395250541212488081576716833807248879650649362171107666776341430534661723935291947760015791546044469452363961895420142561758463985262985214902182739623920284210707167192767526178841138011634179210631980347705048905526562571093675029106563005606342950051013, 81184744346790924098390626343061862533926196813436264423392782313183788824888005366960636464932666991679250036623225102844077245305279615789985297028151686367395487188181416047313913708495129221758772076767595640173439548175714389499004700598291317543926421962858976817846596643104360539905688568401039734718483, 26434131154005660208202418251350553299645786233494766029878297162082886997824532111995385786035751557354362898428335530451272701789617149071688592843246870280783453272275136306294400300985731992703683476375688305074195262278872080404088938102904111143101067942664642550110639626664123760598968951181617689902541, 20583461169361164936012239952506086042941935876382559469522600586017850800344765779998955301922686194592613728117977392668857817500652927316170071259763189098650100319355732975236340932783385931830714959967369110831948835561327035695862957210809046317597465402541788054523440985447601668375174517972307420752222, 99534127272271736561819944763606095922497555550678291381059549633615143166598789208945263137876687923783077645427746546609553288013773320686523582406074630183160062915395771686193917033832627369751874816677354435908597099043633357467600006811423136496389263128632570405208493745830930161893550082268510553243436, 118512116206510628620173620535467344051381976286214661348788449888449951031872461765117206926632677694087945546315408145619615151832782942014233116281935093137585570386446879683134361566600024471557481076162998555307020705103001626351022137545564104344410566269738892608918426693130348185415804993793721209609921, 39696874135154683267112097021680040753243138159093000082671302585498437603319904894403312138376713524983452218540365741436497014252623022059517764732201708697832675412789710043016297658647765241931376357562085304351217443979514385699767267553378445677211510486519988739144271419362000197607483106320082211157894, 25615713579794183863442485192387430658723428296464586587898591117935830443598276803565696400498331135396182162761634590925312795732761646132215168836455602406883764926399157309533193399134550418083687077959980816090474500772169035534758695041065067455682003512957204985608587710672977761801979298600719822016047, 23793209649566114665504267496369174053459786578228840738712746160813356913085291840670926485938467021921249748937163453045493268190727694834746331675450612307162991196358494672951680343821853030212625697896822806418811182729559057694617576595345840050914186351202035936407830993232414495830287089643357113630503, 84900868031750701719170495739268701340448411132522906627713496129145064055990332922002486194735907569742410314242506161002441004555229668928980128799296166340146123428623689620142768423244946548591211248837198305592226407665478362906541272913507633212921149441249303673799120352922183629944134036918567534983647, 64854743778344461573875505197765202610602120089852481429093133918839065327096609472074901493597943717665732351345476707313576146260579823636441977310462506242356225915419035285099759708938797787590056266006186272630085683224747473152107252181715962546230577202193544842264175396407294764016400072051626879823666, 43786460809814877850055135457752884384516501548292829314979687937607951889102449353983106504856286698338120117264846883578454109760559338097644845777254246143813247771973297517920813642987087609503855062297041188130113307877018724419913492364040334823999299826485220355118533227105208525871102164850743592197880, 18410848816279000082865665087967308434683881846057587302207644885782121929540614117218622845465184222863920784374706231486900135399669880462420214078693028046048021435260904923927365018413834214333078986702654848677487103752777924965608975606985449643730404332158705821979821026927627232457593514769409557857794, 37528795642427381026743303290555251064602380591515328584173853460474597557188114837322912676348557014234144738972886931444325218088188023630647534035725264163124845482521689580289083806870704489342225504049591490404844227836527733261384542641712205218746355586140270679557466938414940696629906671790333847339100, 120184174837129922978041761049752494349805405363915733328766090037154677842877770589616516870003359227784292556831725911705007653205940334469000068369577478846709121385821095258347556939153698007282502763909940256677799743506174272974157274102970394457871359832172736455842603413137518696350897940124898715264328, 85114042547376870094991062686681561109370712951526036710890642223255504371925133357863720777505794177722019923294054968209724320983289575941774562335331869126256931667309246608290713579479837728662330515334593645923196813941733211556279847804080648269475904763815679632829504041349748084243435407170116086099571, 85664036841997000249918266611625095874187200068219663599240259437252325179648759068399867768105884800411762830251668911635511387529518068874630535460984056737847815294298413093595113435496939074803361947656093885514112089591812880957906107416384430811199239381641849560512236254320481734660943314397466382518670, 19868151443713684033326315419488805314642951421071058037081518185917142386124119384204580739191353408815653188976676798334838959292276152979270636624021744528913109029922119160800340250667168104047373320086805282333539262671835560171422052545510197952709359772287020357635465074316209873689272267323257955153323, 51029267901687836725907965568430647221250571180244643611425953900542586039831128405596005089082767047574164924899010105416329727934881100139413736187064637473224707121868210639131044204973756282046850557215004436827715093816988545799405346151923231447395532258095016482637754870243670358652069698049268883589124, 88034211107477606037608516993038006849109216205386189419249337698181850592850024345069840216575652166713813867810010665618768531718281563277119288198903566342692567184172362056718934854721638856943432002177665039289279569277329521972446746782839371702287518786028884532536089431813622499739059673650919651503327, 34290724215292206898895850910853573969604203610446796482457188079779084234166755672139575160998526644200788650835348904310076192206731369137747137479474593487141698098918402805229456473832106349331555085747621113162720499571078980178142378770306917802125052880993548469701984751330079122660792309621426541588076, 90927188279218437043454554956642015346713372562371359261616779706538939681408456355974513604735454447880695728673117860551338566945192506092751947158505621256166944871575026077958544804376039892815849827345907923264667687859857788352006910436664478067757651891635634923727530789609690792776873591562573033390634, 53732343203006760442398433872134781295830656980276609591138146207626163562517843649120913243776843334107106691749493938619111007479062412456809500791493383632196471953312152159801577623906430605844235078132185853920208052494745920119335711435221738446984963476234515199656235009292715443135922168345909287531773, 49031927534145883184926164295828977811711469424781078012610739070444671584077746477613031478660697183975633421868019649807499312667206591889141783516733744766298933391910692474266962004086039942805103040216748384407579306341588913664371259037264104088526364892368819697446167356277559716864693012958967681100260, 30963093465814372302516642776466055177417508152527408097213764844911320991146439597064292750638894222728431395063768524250417428928630674742251008274743494898189847494654965058948152674638339661926080272873883532044920176841760857878305035802233007949695617087173051988751329551256926898662442540254844991028514, 38910112932907768300302033715233195117875021511365865825041254667079681402773472898691511153844674335901286966993706447991762641623427579348204449246293604501210799161052618900641298875451688446687090763591699182741091728011538059864656433159402170621985800117954635372431554313743158156450491482836596392698540, 38443585562211316355274911393358256761473644112925764889560030180611756915515144544478860742103854890487528907562890898220560352513541741776265949250582845223992532020273016857208957223972389401808992966177007678770950599391794859006751879990019132124290539952279226068978275232584696063868776228658398019508687, 68550545600754879458876198377420845829320975904563551687242682944061564106671329644108261571744526116101799247679080797784186089149212343674697695440503566377158992929812917026042984952900100484829086299001655020193931835567043420882168129444729139288226492289343177679790267321958684637995637195757642488407276, 14035877123755570541439737876187097058990065301274722507585166336666626066786310262014548146436251719506889507596006387639929786023894491544460425397241776709067116382427351107782288254085502357976399257409284873091313992760783124271797334837519629008018411961593376262210281164953819570277107742944093278192891, 84973935660270819758814233083142240710785309884502607538970282884173754299778363893310221726403783947387743415857505995412132704938765096035328014089802283590788326117498458965239857137170690424984064818395940808347999385981549657227261498421032954560304304123396784276562818279812166711176719165057986653655269, 127652767021260495264466818414737386226807627335092643140999814315165072776677100093295944121947491864703175075802550400479697578962892452948470076586765670039963843210663006398013035858021917292520141025024089841431675871893235220229330118710120234682740731230605781585933497507868222142730438320650171223860410, 10820660907713821060756049660148560389325280624093461093810612541407581846537858936018021071684134263919140572079037344255372562710590250975822332043248751602294057721687638216684660439386848864418110118512208174355768432871226086246312894904364514743506427898091247247420131030953043354451982106624371303476576, 22509117536200148044923857446175408893075911404191032333097026503103010276105955757884180889706600230561199133331513880035633926105853975206764813984995520499767942092693844323122983122419315389669151529120786805203317761028263320034762418835415040762546573582987418970210522622738218431543314964785802667587831, 17110527541362531877473330877601602495160188646106725957393956572731745660242627602027036247078158084197564066866793058830963123952529593790431750896935886096261794752083336388036458068396262377010283577634659205378999555399253008352426584270580993143755095742288863170042056511437561276980640231653447089696471, 61348969566002296992170896072625129282323865986171588065667375012252011568769255349045185267959292869829157950934447113661709763529293480980845035985257633760151897807384916925942496992692306256026272824777993338140456567783548738678972934778493803536774329693410845609652017903413643751788619405927638767324811, 22510200266842330474614868643482821984644884364293177816481436665684674092037143647321900145327127043489514908412852947132346581389833878070779594530084319995806315545603004624097888294152486960640012202384261073555560735843725251439470919050946837207965392746584707716070872006144735413123120629275998839207636, 50720056568644721066647792700132746371519628076501379437908002312608804539261649596142852235153482308383208999791237037363767518135800305446886547979409480500284980037243584682485311702605225147297356529617446995741990013066746514569978566927909505486404585512297997162119969692237951781374377056093090642010097, 91561944814950778736488535643520052714900101756544637483800925876319855838327993556442983654484996766433049736153189800056457912285338408230393372558184963346036063617106521919740962726456954911219888157214487326900658606650604294547947205051640436119495039170478782141363198165616660075024383933961325219072058]

M = matrix(ZZ, len(msg), len(msg)+1)
for i in range(len(msg)):
    M[i, 0] = msg[i]
    M[i, i+1] = 1
    
C = M.LLL()

n0 = ZZ(compute_n(C[0]))
for i in range(1, 47):
    n1 = compute_n(C[i])
    n0 = ZZ(gcd(n0, n1))
    if n0.nbits() <= 1024:
        print("n:", n0)
        break
factor(n0,limit= 2^20)