knäppsäck.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Securityfest CTF 2022"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## knäppsäck\n",
    "\n",
    "The challenge is about a knapsack, but it has some constraints. There are groups of elements, say $g$ elements, out of which are to pick exactly $t$. We can solve this with a modified lattice construction. Assume that we have $n = 3, t = 2$. We could construct a lattice with some appropriately large $w$ (to force the target $P$ to appear only once):\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "1 & 0 & 0 & 0 & g_1 \\\\\n",
    "0 & 1 & 0 & 0 & g_2 \\\\\n",
    "0 & 0 & 1 & 0 & g_3 \\\\\n",
    "-\\frac12 & -\\frac12 & -\\frac12 & w & -P \\\\\n",
    "0 & 0 & 0 & 0 & n\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "In order to force this we can add another target column\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "1 & 0 & 0 &  1 & 0 & g_1 \\\\\n",
    "0 & 1 & 0 &  1 & 0 & g_2 \\\\\n",
    "0 & 0 & 1 &  1 & 0 & g_3 \\\\\n",
    "-\\frac12 & -\\frac12 & -\\frac12 & -t & w & -P \\\\\n",
    "0 & 0 & 0 &  0 & 0 & n\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "Obviously, this process has to be repeated for every group and target, so the lattice expands with a column for every group. Rescaling columns by a factor can be beneficial in some scenarios. For instance, we require the last column to be 0, meaning that we can multiply with some suitable weight. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 165412355522575736957233292119558342493172974696358093385092849570033577169723829813337063402529762112442923742584191661661503841974947995281260616931676767738982622071152850588263000939437247402037521624971490897334165674377210791512783708193713172177608425623670890777552184789265542025905855681804199382441\n",
    "groups = [6, 3, 6, 4, 5, 6, 3, 4, 4, 2, 5, 3, 4, 4, 2, 3, 3, 4, 5, 5, 4, 3, 5, 2, 2, 5, 6, 6, 6, 5, 2, 2, 6, 2, 2, 6, 2, 3, 3, 3]\n",
    "thresh = [4, 1, 4, 2, 3, 4, 1, 3, 3, 2, 2, 2, 3, 3, 1, 1, 2, 3, 2, 2, 2, 2, 2, 1, 1, 3, 4, 3, 4, 2, 1, 2, 4, 1, 1, 3, 1, 1, 1, 2]\n",
    "G = [[45648615715476865939453798884628383255170503068363504636009519300084326155627778763585231994576335856041873081605830191293580971524302002936556560953035733315550291687172378899384243518029998560166385362432733358151228421379478108858585468259677985845523700994575327406541420133449935865699130291963541726118, 132022252486667817994670205511189608541470474597051895292846858507997489114856566649299954095800968715782590926609754693798189931623448268093196801698416191460729593994441523134934297972889003492719891621467012881999404609912677026541181704107906173283889313093457760173723223609277285349292168186485897711385, 62569299904455633862524070188105404907375329085970612739927494382879174522853488085927010697061451990326041007420434853659690770382661253814731828345275270160553366855775201427324538586228026515762195165414222246701522430796255203046975189255315844743500147390415661620921940322501316362793129356079756196166, 141439693096680062624173377492181356524656867322749223481032166274204553445820020106720683011435067601066842313319995837610860561873761081119141793253251232043011361488611204674671358077076439117899477507750481772146870474225985391154726682799629209058507566149250866063614988421886614975920995251736509306400, 46882278141281061921299401552178264141308072201182399400123455281066781657145406541768545163217083652446700969928780481735923213123646167346314478581064028554823573981566114310442254851524813606068831278744845548975623149557270701582604068507772959330234835296809015915246474498222684642326487343799077413671, 71984262290354883982994251378885616026171896085178498037101226817878058969722659361573151026613860995431946233533637456657305474873458695413709296263608072645252581939069885631841164282001492137110880912567491925525347152267130082047117762866685059599223422718702804121278134299431240982128801575540239922321], [159314024031502536281181565464833019944207767184831988402396802687740072307260889369704685029479332962308861014946928949009790251642900520448965800074646228807176488953973385003187370234009993330089213131549847662199650660805737030912919404339535329238392234394078912161770884704532483623881523545797282694067, 17450398915714400329611162807247776405818582759442082004726564365221681717012148477693594872043520169691663739773633530195941360974477987502160806882184660186997943391255361476423003712391867338982923314277695411445989190849005227872938874132273462254253737047265545553580319955971143456796561602832591556517, 115749316076022798770578450688841689857978894209753262011097366681503871484700619730120770184635024786713970592432663546681484888368739203909464565836558270697286427203055837758186130753686305916546584441993916059880594929013333190386979134969229761355809293646041001246695153253764561500601350371942438385250], [93964113819731732088320633752888873912691280598892487729912034997948610512031602664434787993504557017614851188101567356453261932109007653246573757992491784605253783439732415812594435139611879431741630383135003068293719730754611414436119494676486576576414591160312857096000597315782608822882593474565854860661, 1370462179849266321245007074412307441491902712856373890655716034357196389070653030014467121207992035426299234557906355567292855040761298969261400288166636879092447605729259367715428635557917892485039959528903677199441255393046181059982819858035901587720333791764489745659371538358939122732620554536767455047, 21336068309395901532039284530430715459041433972776893267311267049760831388611542719058558066360026615204741935295852908821867112967958859157578752734239134908086389785385283483481068359460114699864252420039226175511410224951354361899999148633699255440786352041872938006068790332965289859736010942932523120958, 22944324346650622716770588305944149068984923432583079318387307604778993027793924912311783965946082678144947621186065602891864728068418459256412171370282637685526242387526842497914236360867728209056411017248223758058784301442512476099895400308837734475925303901662832536968768269920951868622527730821260012378, 85514344894268632649566544281380242365541421626605441983464067784702238068789320259359064958100447106884304132790487040998224446626575793372409112131103263313552449478650136776080296703098108818160890443636776583467997131191991883095011068388954720467265648758141682581096711930189363766185515176746817385917, 140972104057610815526043810586830578809454937381686741831237009449150435508551909095892657313118231445281304145853076659260162038718765898891566821802088195592893157756723058079032617160451392627772083118388005037239847424185442240859585985001647866890085328857419295758591531607753656356129127855547165290346], [118908587916055023276611028593592723139819957056525170827832491992468279035883683748169723808615545788164337566509142943784072076960843875907483046562567627633208244278575761965033682425476205960534610304219402656087782174091357260248483465861126149802448617167093384586314906876424315565054483598890105374135, 69923186442489683999591464883343706005004757810364339046325829214323141091366329329490661173578780964353581856602356786917208085814795435166548499834404780418140176042079800937066683441437220197788135726699289988044476072181933601860075464891320793225303929294738608924291612125772576711957080422149384940641, 97954403338401763117868605466441681968814398451386977564393412812578623042763180938370892848752761010819381858650989282288263064534618470891389824596635331201167196439924415575497928005902927515020774984323118493808323839037446043537826913419114783183363688030244304180913474423550010395032032915879117698390, 18069545196425220496469179373362605905049937271993085047762083748748418777005188219330056634249038716032888787979901381092977670815632825601063364414124665937632480600604251980799138248281943668952683938738627002013858286036509070401164166334755373851681169517365377880880711652148297609620361829078975556724], [41317401448440685326240781398539839860874834029468605464133165037653154086067791054691688580766094050138810405352570665655936711694322391061282845031451566682479762606665447359369589072562105961343335749160856437475627196083699594265994042412056224519435055597714979411496221254395984633773517656404315256008, 78903688944577462889417290862998260675698204124931093285502332843048044270916374001977608840822094983459449671673963964940511329278099606399616200554592371141791868213949559307699309689555663244367336653001060737943476951595122238983032036727586978087928417841876167264694255883497412339731415387468099196285, 106263198269183921943033827915652746536525557151056728506046404840737860398147636873539868750943285975475194109380040582976404439024654728148084352945475654260482177485684068473189252145021866843183041174992382072285124867136707292399821526134973354766235006243121327904412563152586212658392706760752683806202, 140722777101872446746180899904667619767694910983934348229032359267608665360638238743466306262623375273752145995252560103679808208709082910676714979922902467467934295812906636296989496415809060705412709029131309825065756584651744144092437234293540252990815837803826179736921545062688303583530191033720141779700, 7293247255428315496734929956215881019931579117226626980497043024073182526937049323547244486904049106756479174176941498719648452878778487361709841190964699419941760801558625297385791987982969723215516397183734502479583325623751376170205151589896161918358924736013330287279977774305237588222584588379708835340], [127345419978575613037763801714617344597822129461829689966570528467747104191841289684336117511326179082108311778507388565250247770611026785338666361574644878781939721412222606256906240993620186634857168693592952733087783946860635358164009879766067169895903042020135579685903349619891254093141975283919704871769, 9449313954727243816800923835720419806795978773380905850684968756365639084058643072529874509212571390535154066999168628718053948420031768947049491179026632490742673713605277479077916192003403153932545453309012990393757721792897834843795399800964661913888662530484465230983240055731208194103897240374061764272, 160237557675085734596739413491103209730984806613362936776185219820249731312262209181878315954215687039211539684088665107544471875326234967519261391523239076134439989605627818078331606926407785187499216462974900100336561780434014069898216197749708044509740796471063657238339916717410964490479518991866522420072, 142672768930474179436526890352900401364925195282286051726947636618452144295433251939190938497252260401301603455699362005663580847086803939424308904283204962012981554161131546432469497478630441099589427425184626503946015237423271463688609881772276841885048441872556365763012334734134509450545076858831757114432, 117632351891117877705279681053168567371171086150430371998833253270807889427654166852440564818003779762024764015876206053843131017250293005141682768025871162589827176220734734988472252524035469082781273821110472816535522662074297218933817491540014881255599168153883607578494760918739490752299508444123045157430, 117678870626108741553337074240176426214354019200648935869972391027871895798549869298959077418236555976750364231583912605788873142123722546343055257356829351309555029011795799272216158183211792491418191864746638564019059401473443656646347015407694162859058247160231516034832695131316704885323950245348142814308], [24441757145645232089460291018313700722313790637209648619982318213290992933784476826101561311867045860979807915474828303991414269093627721531604859625834588978148173836721604255523906400530864499178209544249863306906194224118423066079680723177601370480445227789653308893189257140928245259175470572604366890934, 18570058068720299852105893332574715608222806262496729920738544141918788105039374859157497323417292537234202155715570447198325849020115143529099951446820516162327947591941536257643099752515489038138464941360511265498622709797905487654339112935489551530589819091934743942608471687692986381300958014456388818544, 93936379359361709106545316080407701166829108915933817883638064710445684623195599154113098726122997743472627479136035779020153823556521500809359675246979942481972891753331637401353701414485302451189746542749306386961598819629311294165458924420165110959007252600812785715923121873378252288548837400019470164564], [12750964081890734047397544558730270421959244872478004914932376302853249951422677838966518863320072597589365199580497365826042581359087885834590801626976450106302880292650137883402420455122849956614265997379221510890640921690115029036902964004743024894365896659401418166928289623137100139955931726918759236259, 161033989889252216403729774186483097130256201627749095803006024021023027854446431041310803647675196959019894463542432702520041322729442784496553422132032972889932672225476459718282774989422962586363979843165956711012427098671936566519883558702085520711521320952819320185116002221708226766773944256586036140333, 20148817040468936389779101634877717429226370878760055616643420953102358557695889627468018737239584060258259340258389458076907127000822061283262714555449080912679440585506223856720909833381200103858569083470563366808617418169044273019719299063078642125527225423094508807220278704732030702962437482158308305122, 87354679052426821698968937432368191626080564558805620959420446745814483271329680850593920990165495997849635522385384148703315382430467339225096434179406239283771447164685935747657850710746040414721659737319995432786589143413936166261779511925905966278918467780619402986772928762619609310070614673001126529032], [140070990514373620707889015008586756201154234651800615641960920121298166350582468561289910989601518511737195773909388575923051465697085522297264985222759602732125843596531206167107421232231755229489510297759074590604039323280987984045608494803863707325461177569489750327200686219523332259245635824385294209937, 74065902412758185271963696781473475329410932421810244703468959833181287446625531040383770347737012491695879383509875670249572533027920806056888944151372811959604177096551657643223646730348389977688231958605816195910821790976558946057627588920262684745267096315282706507781697658655697647972679071351699427014, 85305665375963388408592007170195805321255353225909373850554081828164212915658123516873493560893480418802669759287132731733492021084632194202292357673454755968288659862569824493703665784184598462655830986267379832967626649194571152221628606601569661795646493718468095491763412752345510803531938606572731576926, 36952504317398560922544986537217894556875497601456459822509265076591342483800702782668984703269262780291277835997660532441603976146720054052888315569285348840372849340439605580278691441383757784099900038322070296609894946238494611719954861594350706396281986242416591240625489994908426813539668578062174434008], [118650939118223240316699348455999663584714093691505013720548337381390381519598230914750806731072942787792743793962044883397876536551610092265119283199461612786294658858695191731838991214175321439563551034995523794212530119919770949653310392290821844714918870196311218549372676071045958944886740484649391356322, 92424340777917107867256805285386005908047494184539806012809550421216409505751908654102921616573305112565331119805448874094584958896156390552658199192238162567994371073923033230946609187961298306137199410073472875871561122047493023922577277289883538650533207924032347125514898100056928318552063308904867406983], [88312582904796640061004240297147529183385121319796449345265968478914591261172334488053076830951667264940052966624937510780544078374188461426833785709173921035110292325839922378662724169310635041617270129112272268879599005050075801010758784037503388164310466960487488358492997615393945407544736849759699555449, 154548240143923685343307743034821328052921854940510726970980005258359339628089175436680606988960591011727320176889843797798134825448179904758941552048147700106729366789524234199569263027479463264925104795374301744342686491629836098843865154257030721750125864228115012288940114377247083080009600401694775678291, 142747229217359264991931663454454373747907521811211280771268223822131902394939678880274419767781133344638282581654609084056212784888016137433469308725808857424989860060196211698691283756989462752746265005051409268913136644684103526237225955889352501011617957525686088326261183618221214548553664103151192765891, 143768435122072084247678963445001011844379434251379377451709945929725230929684333661836301177252866010084983724053594304207920466571490466736594929681147204732500383704935806305147973137252961362035481661241103665419800445090003407055360821363474908498319464121151345296961029441011193501426587396893916748023, 120465126695781193344182105021848063536926797687471119284747462575635211556110216915770991975420431945232598259614704021138545850711234056942662977721312682395703838354670425612841235503829436850559265702740810889448063286380527267033816799765412860176906038091585979176567265987777918093364166924097449896537], [73385865950879272078093146819914076447878135022243344920230934141827616988491093113475186173741954409755987876964931499781908175031376113782103431031898227980865285138685360019582697365686936605600526425862441377787448136902602565204605161565907167391047901642610553744294327656792053793372293835135589956206, 139369107673672063792982038366901633374428807360715553594390512517790652376166366551220813510959789467241520373565239234301399878512782890195307321358622265757208964550264613342053800104686577226382603725472599604313222998432234339543279523328632546593876986320275422570564603981773119115484069305932144410809, 126199887552303537386624551735870446423886836523661683484722832355054344317188133525549938963835756254759713730485311749740185832621360059412862935879446340975162031701952132581049261889924221347856881360157602360489112885727569464064471623145922559672358283224731443636638634458519053439903149376974577995478], [92492067374722328027473111654418537835117980004979865800266332670012177009537719351213447827340997622472667214198716327727750441210932578299380353874771616403289136551168811498071851703965520209133495419872383531054791067721396007380077147868083748641855193644212808622921577208332949230462275566641962552677, 149612403234287890985961191789703304256936284985064716739525425498920187129253565919825983535366049527644558323599922707981661961904339420613370416999797318372040059299150471526859189845344852956671570170632879478465523999914236679977089164261557598620099496404310556081822068467571540795405833944935545109044, 70118310570872967425418738948805628360256223901290738741058890984525055882059964058453562536190585514297954288627460327719318168561201362283140869513054656215011575587792970766671135064702858552007701927941537735985876542541493778123968099161319866363147011492366821007515417034312986208359519921266057616612, 24558275814610406490083785368081036463233303976471321768317969286518761227978621669930277053462354766502764235563024461280918675306903452154022704420837433350438615460337135352921158746046117634790244530078235013567187551367644608870564134274651432748243751373567039341130720410434244895044810320735154578969], [52228286756407217056280735725429439358611434013293686000603860333155275281278710499900616622854971883873010627862400561478959471030955640348727926892769857753056557016475509969838861428424371826802622589866287740776346215933148806201657803453972350372129086747160248308646454513891446634219670690131846278105, 83509442952133188223443223716100183237825417672855380466640315752289358416459682486359385470356524550819252812704301439073198784445312685035522236000814475360884832457838432387183191506896574178013085218537027305447135433760226814665941289628483320368298895580012515342675334128896224047212113308681604070779, 119721892910572747822728643083329912670052007024388929690218807023650254947234672464803117898878704274207992911018348622952365560705874771143816002280706940886953630744966585768850610740795788719992152197723911514138246792339132131803380051301988532304275053942057246143063878263230049356987158806854687539520, 48521970406246115360037942351826725721763698294730255917348687667385955156116480044040505552299040094318358157074959596069115844297051117487279814167760832932792229088024961543115909933023131324729797384076119600487889070396529396478906573906076607601452124875476917203012857759167739756681946135758340297289], [110107467118609456223974334441261342963135197532555036492844972622106696556530504152852732678366248049291121735553272320699637876898011513884998710478755818723963745485113479788687952211546319221453416915512627489477968514989320761252094625143828438445903014385935691475746811198852225937660367851852547431101, 103693166036012747372867621406311953046211844069359502051150166384503192381731937100530259685976451602191547751215294742545597310349006228186594226368610695985856716017936400621081682369954933885482471340432837461541327418827619147989071183133194959447490948133684317838000752804543067095809610730253162555842], [6129787225547836709581177998013606338940168502388266019084672703026308643766623822628147842787065337382940806540468273492510204680508870688683712366027393556616631719139433286642487562894242253203778584442137455256199208705915963975662069383385141131627092548047231648672110199079810355840508139927284923736, 57018190882053187744601677764372715465148012420171580576369300194184097503809180872936011828419044266964574858691896810938675522623175419154515518753092136332733868430456370141737460348653351383965845386244762986474152217206440136086614957529108609929473027257335230497513073051541391342670357531360345423952, 43442965768569308128356174310700240475472484988823958459073344034596224292945699060600005821469535086359823545431907430835876961709114910985638691434462578914995683359130429125490229732756553410360493616434306548625962234655299113506095513242222810038453214421675307840590971145087718073371736488343221095288], [8064840634942776066743224039635267576635016738645508485220785122282632697040601825515080614551260742305779954693593562372134671947648990691750764039603578937199532770116251390765322451537387045099384408403752655186407672297872733773564448789384251350377248678505295083671883976099854520626453629530519876608, 35564377709459909343305249600600809086654770671692455126659657531432745820601173738660044853797738426403852788733509605536127492370441031868238984233376220975408337201121940858581283610909305041668150825499715145550149511403976009648374380460215462378257959837200802951610257172627340118345292714271563497961, 143929757547717209418740212001858486454164986439697256271802606660932954060148924810602374962226608442345585615858593482407065907456368789970998123333594903703339547891963787993781473002767266220624073833483689724594768711481974861946623529676839761721500616025542657492583244572847529000320661802198029193630], [90065742308760477890900811717449292550483438394395055812913179731179597831241854830415325469690528009450579577287845858380463877573008802630968326270013766487242917830677341142823617345320288182976181023757026921510956722979774669513611337284580648468554122285820254099481563067512194345117062646581384565930, 67336596866170624726703123383663060956664503552944211640035607487270827306305144382633749726744313935627406426874714085553609139503130381913933215190990998652272076764097066514279271822154253165080821847709087809407215974958640859270304528456387015138104988239072723153320850475930895227412165486979200757102, 89791140177214218899114470761331373049012754515219005296756563830809357354996272206328616982791413884348623117985889606146446336558917848761138062188897070632425202717125022960234890552722137010644233784046997597220265188641081341146317329839823492857525031526382114194683566313300136872446154691293826397979, 136912892704405358806872063846971786978373237006052136760655076251617903570520631381559968248074395613779776934089143659956326024365829657641703982844415876719786056841705170022148593540810792627331849564597099956107200389899017097048876642381229493608767887273513516516902704572171912909151772027180372708342], [85266396336494256249013459634226123801788835130601423542763303572985841072149396158912974234703621136394312251999126344726608601610581128052651681929689840749359944245328470219315529129376609757291490825548937287161827188020162851335072092727213664893182672140834231626207424414840988119224210683389780723862, 48407556142304051810835454829273236809546534830163279246175511440813608616977737095665192067620744759984109080973803675107573879874291875714223661371566568165956170303819379494776620523029510188121931496476058597273202173059369060080782594951268909827765409350834333413680424226017602874403684887362251593161, 105464069641012231267125414020161457375798378243845237997888992061334986208133355920242536737184509998345641437635818728375327420278542428039583891817496556204519487533223982996988164643395704558872843172498375805709233676950528582204921072195962714157477821964533396247272687558044285874445839275166753733508, 93483624424013861751378580390112291476629140781044854714904347457802738788968431736346869995768224318290192122293330403322279497547102963287007200072749093832986535195883380634591479266105278316482884637851338865412129071463703874270077167506730792931955545609803123543401215474999924314996664583103718000032, 1089961123589795085781494828595658860774969571445667349239345879452519149659881365632080006464045275491543033231643198998702812144717901571305285898562406999933824210723462752468957039765905037814661318995683733769717814786232845174281640528668929705195181208709583246150077607251761698353813015510233507560], [85589959806690205454405822703081796351115242224795084693870326247421529227914192439998315600065135600605772267714346395863241497848523841575852187681742111700558639688927532848904453740261598668792944364589241299881703323403210529727500670815624454252423450610670519889612207249755004020530684380545724141031, 70000655255439275031665743214782534547490829043701840712140956926964010465620529979248287663372286566119207307982647769944711202237549807707282698121283847349090045786775850594980638569230629904748641952854979391183393797300258694071566783428264084319193520334045076569693406379696255389864618005857848976500, 1724265146851560589729507467894544445790794444909874128839906691816216573472420907439888362703290510767820641426496831746832507412385182855275948764509037934608459875356651108024371995111544653409900410661279309352112598548721773325777164761509337826443172402618247607757874990907300119989416988368821214130, 145242163511916744124634805200822884465545296007832767709203553737892725829582823360993100733203506080892468301621553685155590499615620801301493971779401529340876921321120794788378055833274869602293709557612161194682222885104807382135343593573789573360272090141149880907594227879561406246209051801676971156144, 159508341802340615931738033249393587796247184882053264599472039645952215513158446547661643350159087680465696458168779492876090565849259540508573664396910895183622109558864695342889658512032374708730683703842024074622949535985396717568159874652477546858902603444313412650637229616814662097430627141217526151959], [144442837057063864911182869062337407674788898823009649943417804555578629535106179028459980738905830864683796949234280431386443855838313947472935366181193075673927178557696661535001545334072340292063505406347489234352080236252477112522402872553666355296548206126949099291536007406266480382894872204362490371484, 20906239600568925970089539646335393798509439697080270189302814149835596114458391005684145297896540048610043249007648432101754190674286399100110573581099541759718111492685765217274182032094291594541331126245030880848402631958664461001809481124208759868223764126794187251091520734755663022710993854098631124446, 83925935064878895413175888922448221971218121611495808883252687484493381933995970217962006812637709930097543634749463007341287189543195015704014756694073861906313858000530250423850246598930463572872153663563647750918427464831400381023368568145336076028724985859327265142891483070913996814880010703183479371771, 54811120696042768266048803914185167781845736810488921840171710489708697935477296777901699512756186151346024674867906471333789021892934466634603163197504800836227011846872096253881847694257016271544755454080905080860244809289927237868008533385402925253620995724737438874873228152325845208924318372217546564214], [162566412870562752489759715461539300653392329106895313556595863987780706199796654577863323455084610863450227677321147309511010802750591695975939391872724942141358445786801165372371481148592500017308841269597377189646470065806572658726965963673505537087638159693461812236285911543050433505682260694879141999604, 155777179925255057327433456338024496967224364328912306000955574001311790601426770366114497374038170528577439003704905322085384672451977759535744994327089988760495059429009152490650258048886176536698838797278246641282079529159378609030743223323199603777690024013775183576930303608884210348521432164191825985310, 136858077778548893536549303033025824127919316966215265825725885420483419347533597264735319549561000053517939255225711312830377758447980227369519525021849230910210022635019817735084530280899897996743181324464782126342822748789075189158177027886355676675809961950155104333933244138900645618125626398423435211792], [26860881002114386484215528823908140290729425167559293435211727094970196150502083255730215853305867751380754183824585499258099922776151464966009540169332351783825089574546315287519218757133403771247634171074309737461495693612038167526733272799466808309391080927663921908916288010568341426609944220533624489722, 91137355195998760670623473501903052339540736431776528211272490928800564590840487138725438682296042216279907436687738799271929512482926687483836430868690510455203380972705637769849596988784129651287907574863360049384886186671428154654272036242427578498552781193042997117859996195690418171683046886192111434443, 126671886377234334301654872559918573115722737790431424303044376650067386589483389045760780612129004927304000424276677604385242437953958460410336290431246308844851666540109051639843268633907020277987517775578813436804209100221697719543337305398237078134972766381806377940989449206545608577391646896986756155809, 20679074398224073809723698679616217300659746740315804249729139332914117033911267754304861041091389835161467211507439244680834202593878462490220083520296372758739464000151400202943591256387507104413815092022437335091686466993534860515090649994306699929703215274318242573866237384360070367136592497585819993552, 132458038389377756435078774640426159632939903481704645175323152193996566509981732692689128663203127753754092865455713087208193668402383270669012117124941805530776384923277987696643588063902766746676241898856403296811388358673575794271884062168374176395231984777418998386073221586341614351649411123987467962725], [160494783590251793029431633974163954333426480684835958556646552423162852671623172775002659997024712127252112505614269504594027469644536283141963493546430788207589906902789440275039795716105982802047717396708719956612775784794161689475747507874862506786361984053012501868608576202825077643297401593293470772478, 122290157947829812243791678023915447295273542407997583862131557460131945246978115375772847057893570031719280349383497997407584770645709993183842901396990099453523786355916465558520283831669158378260356871960304663306912716113613694703067529706537591237029686439955513282609213723094951824865174377462198053223], [60341859102822713654621035039688635585104827653588148950840538699644139600285630406115561985315975556912396224811351019976825479784166575643753422869396216990126445029514319031742299909319361938021012013949221082713224752392051200273793570171605924681287872071894482866956482074548173306536318157838404682589, 46344744079147829129375102968973604912000110937805176474622144245226667804637937174091032793199085188807314675716553230813902585143467525386158962330773603127910176936035517016597310068645073766840621837038923154929737742464596002770860152633471859816389356290090092013256987115102533477439951779735858037177], [118973198736894800760386179270052019993336043544682147995657248401295264043850799430696388111120617478688384917762076198912162878613680853630202034026470877876800966092513980297317249562386592088730972494966819152956695426910362383917406846134435564610520818358122708842731452404134526189093065994072159109916, 45276995860191605226097431398350854987385110258952702064228083235521294162863970657536882936393872456153687859608308534449624168417834617609424490010369015035489283772575519068167098224578107481959315284811898819879875467430330751580448488421054315770097668213260980147632448986214881657800960979723925619211, 51689861253600704280710848979790024286778477988349223607814961690671412833589681393337409095153560444047389984598591608206075775093577040152724621174110161814218782422672458052036917910970458869284416185038887807281961782273105562859825923004939452543711114497266650517552297303236135652350713349535145890837, 127913545447934638739789681407473773974032930021779613436843593667787227690952081719288187280230228087454619897682839588003272263262534929168805727733091073151164770040008714005968329839677406608076530111205475615595496536941996208328274331869183779226261980843846227907886635768160643823352281915851798538363, 14796059181726809243481851886640433223965764160005948789006534335696596529541055142846729509305255932954423690598025880664260811504326344875471243246769926208847568872335725422459759880695825812308929026820490079244707855022594290002740698773924060368552535526526705774168206340570954034357397754356915708825], [94252733453922455811389213245448615510690113325326587467297195777775594055260992011364245455946492663118762903821017779692634492850218837245710686412379867348782963345412967061007091674631104261908152527126434559223393204618448028456180226137265202171934916808223347992576674118222582570430059852817339429908, 54002375834992069405582247947216030631223789923527947794377270406082389941273659297372649937342874673416913048125881528379718816560369585941061878649744400536324807309845692708401195551890786920497548862226270498935836550995813643872220945530988839624868847209353475184406755581615374482536087095100212359921, 47637882432313282313316003082199447695512606485051227556060421354796100354016866038628454101729515777604431380523845556557440221327850374185126438743508339323238243646942403962412317681939000267674043184203715745341315772733461892112355767012533226077383158617292851477722730541625854983242582996430827045462, 29387852040026415645635334163807374505966803531712839090764618326881163275513482213008799997272128963978840848947535603918327876425274626481088352079408532384133592519699701152857940634077603699704371573676745012910883600010654953220944233009712676553025968931419195973187139953571750474924252671657467329027, 24031470762508696134644033151854573543216053126077447628192155972293209367849388228883156430112313927790575350645225352942782503071609196831393583397108642149719670660910014782544601414200124699646895246834884561471338318916550841050371205917599561996441234435839387825367342224730647383294054881956518662062, 22223772198522302907400664086072080281495645927677316406444868076895717984426252707807166424642079740569775495524490276080706471130021747875683163133048385162337813475299378433279344582366758465938572016789804880798931486734282093453099831005864122019202242492589239112741083793827283464651658916946879487276], [3492062089693374111311567537528594752168954236227979092030272801979640526694448142078875383949644281735427860831324656202451771818573553664766432022554862857804454453223208634886271836581821658022712249491516420815510003765522621875599488558233043903884682608065561737273752046159990023394093944947598876884, 86422608801410174474620295499738780118147121385075153357922963079035117665864275782471017476277717573053923287398294928306248665636557698961044897187695131685909585268115473941822121255848635631378118236123308863869794412294232399664295096086691876696266126760662287053042141769747615375035758514879752132416, 84349399367719474387930245715188678172601156715167846259598790483625324646734980135311036813264271675882678315927993174976524625827026151175817326670519086085565694870275541196290810438446571718923982103427628065621847166270562965670537522867979625311661406544097352834023165734279315989779341653202026489309, 106124632530615840864885234763980693925810037844329833610473474958878283025127174435244067351319084613246034864564229238847290635328012306543502741779244413952732821302459394611485733257327915161709924258547033276877228766908781723572027854033658575955324060089720493496852951491437392062903656430961041674923, 9338933002803226846444399894929719390151312379975342686356881661788925060460307313803811463281510865302157404196554566240669356491762692277166249168326989413701167878013664784884950998964001335979291863560800189707703576474489461741920513015889279533199413104947039087693046317365662887161307521957805569938, 155188240767670518727086161206015371504135315205365810103098275707526635641237726477130205658153561155230865775432301780940017387755338019552419683154753479751885500485026726960449568302540956637983791930511897856844452221799835311213257003337942705762113024012301620812687654076451586280976636012315317839979], [79575711898453707459166440149526583950757592427180856593736611260525623647906107261273190855387246527016135461559791217393393992194707050898626071784079078263136844498932040803326622708475406452746433011132894210801736056723020859193693293759089712476089097252016065390900174693547669606783383227884822702428, 36024941084136361114735430705824016966450698086362081019713704040713000570290747240382159518113128790928041093987265911181515920723555839935219901403104447282908972961169873012755874909367596378179265561147553870763394271799745854737219513531429304665764491292436491276919873588836586782278737196841595339990, 155263615185807572845065479009607321745730101573857329984170454872348183545918514074599864031906293367255562767738942653695298084580302943569659683242745211274974978851034691541383313966985472578095550558638204669647636398528377064359812561398067384066814490860259234904849489501736799901776022152994912821241, 48069984500152790444295107498846234855128007745203341058910094902870940946554209238669273701335342712186863037672754651298223658229313409256846346912590611285610460001891526761957282669999246320343275217415417124988620780175999450019148760849494118839995199892844056785940101478491815338406045240617043041286, 68565544138730446654290399040512111359065334085410495812222219997704737389058353435279142961222161190206243448097838015162149369358643445708716170634449737072302448431841266590006844986537392350311815340880312251525412497776389721720985100180792542931099266711681009367371108662147109890953761574001718101547, 34888534412335242476908797998917340753499854504171074242769242656507579825893071627613015237443824901046656185880512140727723521915435404686055016568725582093506701587222723818152757299774133431937060321056829657658713149610830793897934826581123673697415370735747494356937843990723286774047671598659846183933], [112810911202268578161192826011321289574085781572410497464871130590298264085086716242348151286740403377410534485874976977824903466462000988481270756549878549271930019404412238918995451792840038210573139981836172592981155269911325193639027093767615833230015830871259051163338338836686513841421325518388968335390, 70217199804584296299058393202251956632102515549814551870674899844461627367624267366509249609286509038211553795855797923863578467674478430768689482250735589691220902553747895801054558612510882429264597579888246727830173970452647934546022659033998302782772163967241056262521117131747606830589669838556158469253, 98925595782975916820752543383560271487113166783190900470396060020748698795136896164042478128815282341903041268381864557050365401532995041072705493070385320349766420852905184321840415960845340918383147061820281112420598676462998221665458084773389439690680333485601707675490090118505762642331660717155991463077, 122723852560310742902492622316604330223954153932641396512930600024355985273286018904250705307203495992095949625412778074247774854335478702848111882611595282314133408543983218960595958729897337312843971664122837516909226252436688135264429778584154273647232677447273512067646524138337289005419364034635075477028, 160809706309768990142637599654478844191546521570672028157106080893627040472229365552305724046123018113074611282656364372222291445887272394554073297022788168089397031134623388110628473885158532061117327755808403670361573326338066064112144742745611990994538913984813076401330674365529828449893070957093563660425], [26000929030776759477199197559656897918416272316947012325523011355144977697122396720424971366161401743507052249571915401950644026015410159210403255918029510648729275812218074800069138046312714813199804821014369956318367329961334185344936894916133102958989132823583986191984404105918438545526469661470332795832, 117412519609736560212141278717502593572643133660622161673598416598503366422345322407427564274427239735113850267962014083934962742822731052965884074351538940955536697241507972123233786459572559411533065544801464382971470477578542273077403001499402108500651367501349271944010908057647734396541366312287052653039], [76186307924513590807710912997240264588967329453675068395230499043321400733236773363630823960139341618544874033517991136895333166103131602825686158212047135268566819271214631194392933865784690658986295904690564774735073790486562170732883925724856930311883569293659445363214240651499117245252811155446320978479, 115475817680461378530077870683642365268688166583707524620117635245684734479563897235985812685166230646736194533376889822474654769403744785241737538556642531284033682203331853879729724095041151980847370547179108900469718829562991384341244097756236772294753435529295398071916974365417525330995624151579277904310], [32600172113956710192205968816030292657343059820551479667186345834911862804088468048717496369536371670247917137645325111754385600703227684877746595763526951652129471475361676978168219105546261019411303760589027125958761571467226919640580734481266462069730486014114799268361982459104811722046219699120854698563, 89719820479431151062154049937542498293400517666901100076838013031519039099994954793451913495127807490903837181164576971931159074335440967470947352980930416933646217547464944345896675801061280047964622855652726274450023226669229114469816919605991579588260072499700146769287889418187866242605355842956730298825, 147617056300027280673410847985706977250163965465321894317225164746282074744926003182249836238943260830350734445991651137701228174073196293417587463383212524168444458934348479944296289935360021904390082120530381135217927347420583253326919984539424458749411336538332070380130149549142882224740795827845963923968, 150411063458460994194622287475514189180558614760285950611703402870677339879219008182384183206571205491821035553503970602196434901003130986008895018000050081708028912324966869396927189252009058241432467556592897022891787129874901754652714028030586313443889561097200803023249078517277555717680503512642288598954, 137258470767896355154385636494617205499017513854729933239146577992233279130227239555143716955053243901483789006752301193100090724673050920286299012682284259488542346439099512810871868242638831899802713108062584115465150973115512599504903833133640467550594500132987442359940857674187186131867293133796972468990, 39400461162990946569673789698368742711373800692779570946439028875811021311275382911322115910449014017805587203005238867869216163710113732284124136731244168387362194925521760584162907761253317481615690176765687334150262548376869674579091740781003313806815367790128806238319340862765515263194147697309294762747], [115562506221532156125448154788098189812095270813921637064666943321736159234467185730973957724991371019508574655448141510659653428142024099872135745263549395732515006302345921955702984400379037685500521863002030983153869125538298251025534581348564372230278006938581852510937176317753242110265888427238349776852, 60270045023959795196074998120974648216845395446538703935131658506009375841553468148577824652186640084299841296297455669726110672126633115310506990234092717747653179768754083793170718685942693388979440674883561387483077571395555060592741205681702882033610104199069568172363659574351689603174642442839470301702], [10524033784343745989849066627440285708864793746715346169822848672201559562453357635059368558862191768670503167101997829288313262935919031700922188440367309908543738715958126797916832145604111649875887420177930861085724673993355798580564854703685095054804154007236792186951815812344491103912285214653826617662, 76652956129133950078881655149287708374131312641099720823329380558246913839520193305011077753565656453177181386737910456141715334968756241659699761502674578938850710661397321176803544492535677073067007433442714632106839524662391628083621513986725826463933731146610791140260422644699892963923343562457806640003], [95092230538093022250060764335428952669360343275817389552521161852072279935885697958895153761701417046240988332327197652710674291062549141028757602860862816290222026755569049786018632505840636289163818859955895121247843073224776757212852937331421132618535254092011685902070669492176767810024511120309709985412, 145928899104889722517435076877263008658346151023945932753200324244666550750594437953169911239630587135980468056466584170080136381758698354816954993840961688874588347262617103423401368271713930301295536264080838400089345853296756118856711727921172522162447549618672820094693631913837954794890600655014760319243, 100644733101634090225332732466876459114697670107113007952248038691509134536072437120252187025975873606086898762614312603149853521739706765137587346819569448878849482357507755535600042517239712362336402910669939403622612629711251582112175518208360986377976468281567363023155230548085062698355508566052947254249, 28100225709012630172799441519442711702731342458128713583182427394827917325196258547886497997058520412656876164344331525485765333317960824828569549357587127787177000549186940921424470497213347179239515142581007381947681437778849470351860286271853716736527301244230599038114751551959541465513406568378340078850, 92556357648985488233677286732626635751408548569013662717913772912757642636471519792714779963050497361922044286921170599245001969195390591126587573653192916852064066874883863374048897808272422479018647017014429418959976995389536617652886480066638312417897824735968972470481088386785638583253342624710329892071, 137991835796459279551079848070176665067709175351185862791914636288103183627010772068808301684088976533542423141793450727232283157763008003770046307960508717777895677457284004311862080507700989130091322972491414283295454612770086476010113481611526770572020549207919749051039651011984209613712371865785698549044], [144734898504471640800767283166749331115519340849757212541908750528583975631299852983909588896949093246385507601330873586371327373232442611925117057451731960993812083569715449933863472921546392826435239320263996252879901543087625994774822242693213085693571277776262345373380316331647157971572591724792167133982, 55715240438241784511473867626664315958375668149745329628410679112585994330679953078288996647161789340976158854186587017218771070018273224364371730341425465646162590376334892259898134069826725505202489070819524916630277330310378489627284563577212545907004087975974235081165394687693821397491787871186298815753], [115576962366981924091886081761510308460130620007077279285547418840732206631152517693980567599649674645826029324478136640068713653965384903167236316323680346662330234022564907496000103785826193775633480247569081336631136495932298811248001655350260500307310690269303925677443986032740047223404299072367786434938, 126682780301826782385951079451628849063013527055296625186396054625194050982623686533873470200210918031380303152310062212719996566428621650308179454000692466376396337672939247204380264541478454673342695450029996294820647385898684394198046883783213036076504885012120670055276531833354255030632190045048256061763, 44809484049096061096315661351693347063366640682840919574388210843163653641474034029134496448924568508374971916233434493932810111029003961797964231650627048268628005905292796094948053524126121326414460216374716768268279659806440225215322075778294947842424401236582037834820822799193937897102284162429854808925], [57769226785849325707876087223061013450907921502392809127442432124204714697902240458608150810234772893733248386361973139848302733811836285054728770219380905975408597671687189591914212150140880159128372504350721430405540727814171179213473116247712407527057088032880786533609009379253204104294282657552293503059, 101874973127087641251808221201984706935894285516471842128689978971658358700250222301460309544901347102181457765304146734962275805618995368283215132518805458595823352247659721528584167712947670468419873499644494655555087392599703268129682503030035432612985427870304562226497509413120146384731512099945241708929, 56295861029460013258867805787745569779150379857321113386368606562754096059708994864888590942654375842265660270045113043813232968553703485920318618881476407021956542047946888003435766475878680558356200214735839483163101173662213010945577981021306495484540144681162988268267508686024216582298159352283640083596], [2932614447715485669714363680377666895166625233917227252059814569584263460941609357785913654335256389121673210288820141880394886454330676114613135017669166133992441041900085972589139237388037746655576770207595428696298772980454729306696577853359342261072421116302306369172494393448000318516717728747319921914, 93387382127968841696177404788749388532966914624692563483863145029937464046052395385168582241372843984151577463831967977936005227666166727746046753846199153568479864108109949919863640285169908423753427254690776082865601223132708184755563064855051884962463518613649072482362732763527015048717371598708366823602, 108418824881801503547367646525842590252732036828269423922630333098337283462915935182043579915353028624240814407330647314391066390643698131176842412295450853121310867056192895323694365369665717989757661328154902256734305456421271322980121211808856821091337265573665807676612139908940893180817237358902403115423]]\n",
    "P = 146488798778719068033733430858698142958547738938818961896315661849501191953532606317958094912203140032868829659622140278013178806648417961678168548667542624738892167381197943011079564506444659826226213861558233214040202689096831012754100333663586898278413060706520833717718539615326878266607907280314718646741"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now build a lattice as follows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# flatten list\n",
    "L = []\n",
    "for g in G:\n",
    "    L.extend(list(g)) \n",
    "\n",
    "A = matrix(QQ, L).transpose()\n",
    "\n",
    "l = 0\n",
    "for g in G:\n",
    "    a = [0] * l + [1] * len(g) + [0] * (len(L) - l - len(g))\n",
    "    l += len(g)\n",
    "    A = A.augment(matrix(ZZ, a).transpose())\n",
    "\n",
    "A = A.augment(identity_matrix(len(L)))\n",
    "A = A.transpose()\n",
    "\n",
    "M = matrix(ZZ, [int(p)] + [0] * (len(thresh) + len(L)))\n",
    "T = matrix(QQ, [int(P)] + thresh + [1/2] * len(L))\n",
    "\n",
    "A = A.augment(M.transpose())\n",
    "A = A.augment(-T.transpose())\n",
    "A = A.transpose()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we may put all out faith in LLL:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "M = A.LLL() \n",
    "\n",
    "found_message = []\n",
    "\n",
    "# some ugly ass code to interpret the result\n",
    "for m in M:\n",
    "    if m[:len(thresh)+1].is_zero():\n",
    "        z = m[len(thresh)+1:]\n",
    "        y = 0\n",
    "        for g in groups:\n",
    "            indices = [i for i, x in enumerate(z[y:y+g]) if x == 1/2][::-1]\n",
    "            found_message.append(indices)\n",
    "            y+=g\n",
    "\n",
    "found_flag, b = 0, 1\n",
    "\n",
    "def lexorder(x, m): \n",
    "    if len(x) == 0: return 1 \n",
    "    return binomial(x[0], len(x)) + lexorder(x[1:], x[0]) \n",
    "\n",
    "for m, g in zip(found_message, groups):\n",
    "    found_flag += lexorder(m, g) * b\n",
    "    b *= binomial(g, len(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[5, 4, 2, 1], [1], [4, 3, 2, 0], [1, 0], [3, 2, 1], [5, 4, 1, 0], [1], [3, 2, 1], [2, 1, 0], [1, 0], [4, 0], [2, 1], [3, 2, 0], [2, 1, 0], [1], [0], [1, 0], [3, 2, 1], [4, 1], [1, 0], [2, 1], [2, 1], [3, 1], [0], [0], [4, 1, 0], [5, 4, 2, 0], [4, 3, 0], [5, 4, 3, 1], [3, 2], [1], [1, 0], [4, 3, 1, 0], [1], [0], [5, 1, 0], [1], [0], [0], [1, 0]]\n"
     ]
    }
   ],
   "source": [
    "print(found_message)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, so..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "found flag = 2241564344513545223798297097\n"
     ]
    }
   ],
   "source": [
    "print(f\"found flag = {found_flag}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "..and we have the flag."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}