Challenge
I wrote this linear recurrence function, can you figure out how to make it run fast enough and get the flag? Download the code here sequences.py . Note that even an efficient solution might take several seconds to run. If your solution is taking several minutes, then you may need to reconsider your approach.
Solution
Cheesy Method
Note: This is the easiest and fastest method, but you will learn the least.
Let $a_n=55692a_{n-4} - 9549a_{n-3} + 301a_{n-2} + 21a_{n-1}$. We need to solve this recurrence equation to find it's general form for the nth term. We can do this easily using WolframAlpha by entering a(0)=1,a(1)=2,a(2)=3,a(3)=4,a_n=55692a_{n-4} - 9549a_{n-3} + 301a_{n-2} + 21a_{n-1} . Running this produces $a(n)=\frac{1612(-21)^n+306852^{2n+5}3^n-108282913^n+8349 17^{n+1}}{42636}$. Now, we need to find the last 10,000 digits of $a(210^7)$ (we know this because the result of $a(2 10^7)$ modulo $10^{10000}$ is taken in the decrypt_flag function). This can also be done easily using WolframAlpha by entering (1612 (-21)^n + 30685 2^(5 + 2 n) 3^n - 1082829 13^n + 8349 17^(1 + n))/42636 mod 10^10000 when n=2e7 . This query outputs the following 10,000 digit integer:
Copy 9255992309255409483179419845385604076174038906804435862147131271801573863364671050296589603656758794258408363769683958014335858678927280224225587045835554549236411759910608220745411090061107428308955685273979287406544038776309083120692585385738829595466109925134108641705991448085508655504450017990509268760925633701568972881830027061610560435878782702300627297929494871966955716917939371706707268015616593308156496696604916581937050769400369329646318242403439293960972797326591961508734072823394003350315417131956614413828716990680272404638311428692240287388862893111312382911200690775170712470656181173871770843346165473902020842788371815280837350600345873274612288695974628974447382548367670699187634577856102734888566085413732796006178277409299011898018586005894168842976151756634127393139021619117795598661633051521271539523878676739785948001294884571789689490927900913683983739549130273396058399143226419007679327244720322508238328094638668628927305146465933124499123166025607367183896479143811606663266607998143104781472932536517962870064142946144625397409118482948529375842470080996308940228181555868856278635118907503183008759948969042642499296992802929823117992152968592210773980077617609073992433539666043450153737078290684650605359729295102951770694711461980246093793230726069510952832108390343839058578187834443332785573981574093142883050492227667587060213520259865514144542328249027296100425783797607012578290271918793953435463360127600336995858457256850614392061752272722254154308105713290184809674001961254146687993990619053173026936872310492713720330275500652722252195618029796316172978100805935132221268612041959579928042577530526820419119584535052685904447261275310418413248686956899719552564514439618702687638343849484513674694171734435213591420260740566479490794343621991808171166760491608939159807834320688115459926363623951639944589028697445192690646124728566256342389792435969804521066155975776703867010670866905226643086877863465230710100595718033849129799770334210438392357318197622026595775013560170000581836767441557468287425384470655606044094877141189131911510528837751403182546932730981726862216771989383509234877567054461236826949390614566495105022255382856931991575044242339913426032792306478049565359457186829132169808003222243325028652626310095161166749383960092203262812957052229181656830263059054012215047216588117847290728018790343673230003332953508551258024784915192282602155534492742678877926631791253048827739564711644506014349266360429184321481406973201467494658627340758651248713537093402837529826098026053980059834955577271342991416289835227752675490374970512450046682049106507080363044373334490863015296351867206843957520897668462624524697408794293584230426162185084180656752348354284781732407856125955024240750800619775537915436516642312543485650255028594050775824329726464411065155974834914382223375359322586073472902099799870968399129353093933551117138823131500391523207862454881095643216836059114056185567621210349969346322773001970523136569586467928553922556759816995780147911338014075002398099900406865475250060061466196595711092783115852233928711362221294428465110008730032376221811390098890201357718636406741505189198093628817125780661479980043085639258408363072938360753891009465462833335469632467626044690421375033291457334660505739506576025799178496006189196177956994530824690940218609585303782913911708447438142187182926981478894626795456902176806611295290700707265838620112296859471410916725995917774332274290788363516703126067525815657749686032894240952885372190041514195745517242466094437249645852862039820489243179115296739411857999937345382824004834661340869046052653646306780119433815387152755133605774561035882025757872567705036320478601722273548057596707229169819752947743173434922514692459604659989254924691025826519889997310022991556840695569039726702142704241050410911435207616994113021032464407922133128294008095361971182034734357545845729036366311342093217648851382217300855617348105944416959797800045679106051418970936740212201243323374420621407825691038198850295142424362386735016850455273108385213347814948477424622972677362919476397615254720546530031804494636576667039213835518167079053755689483780169794708659175854750079429248450088295652150342673865847877948007025066365086867044327664549023605585607043999489198176552411509573614509346696314655265681005379692562018978024392184039921374721689942446250899039972858579928731641819612416834076914289563149490277258128048991899111474196559739496407766224802408886023880978692457886403296980175876160991944550852846912763591834524913193729446086608083228520607915228071996267423308343063134888427907517509315007222472389958749971119851036755792600655325528041204067006759701899650882688051833189752046173730379687971618778106152429359138121583193895560513945636243134471509560159959342910138282307726776095970363559666437861045509504138185181506053793512330290527298473960426572845110238171117683684041364809195193134404789631117855182678689233515561942021072691997136439472830027014623367190862026964245957075271549021475940633067620735535147002394377565757136258368893655670057033255721591133344504950327269570084772598756931676545313429328183852664697498916280009082153424970243321291245567462087352044270433243592074410354599395985297648098973502854925696106939367723393764563272258573159869455233248604794095580403785375164969409403081664991958224758441901558161776076591761888047641751838451040113125346830296747468600274844343324792391841427920168269451466724402733360927693709608962574594464579536984204944785654570365966337092840214689194020777824352704334046313881288338804180775802282603846332149028417773288289252762349196418160264959236996771411726564554602445482384874934737046588338703536104981717946192703044019694658564450098648845491774640036585262302060685132707254404537015003307098121867501852580890489939024131889401235319636551040339975967238422740240966259515037478254770473708996730051186960847990806128716407679744434499599989634137262723021472296892338440434736145378291606947957568823870560743760517351104324171646786563571781160467327443314778456838020015351241446028925489659469259191936419394977586960658145019513424973791091137643248921605946312129559765684939065366382416571402819258368193526542981160896431303284342924396162774222454806500316599596574249681068946095848501619763049813933785364480427016321396723833776401301274077949645225141713635020427987198026380348105434595680144888649570836956452691173177645938260028423349017079649855941675840603611580622678506371371697560589581420055017577346354260361897276945627730859540343204410331899938007511401885662258331200755215828320367067692873598022854726551625019874259353828693391050015840864024895999795407357598143936695574892246307842161783795560397647511274081780556477771717482679637977149078124055360544607647924994542360536953444119017948371483912417341760402319880478433679698847402873629477418088386984882884367030602730629280761454042804309591833135472741106210177450590122900331916392690960166575957302364880258370864660313841070468917976423612480270717152957780709455158756388635972782046126933529379819689066556155764477143246285455968257184500627209798685519518396787028389456612015798784443980456558550117443763642092453428667889633895366126970127595278029054151815294466903598493508152766946482827975630302463357183665021121093456732176958408682571069411703078859156168396080558652545622296864811704928778418723691428995865934077090633785666707553168035257181052413086259223364488253377812633572773449366795144005798862081976863438611157642682042555702811274364249588365217230773276938197025251263204920250274561918739940317025820821943112146326658971603405997249518942370887739428430647434654176831358048833125278711592425215074394781203447864697270631159656012070957627193840233040056721098784067686855982514452154301379396013592845015085700333286408687000310352955163502073542407384258224528062051710025286474577927921058848236668349074255824260841594925768567573318340711331715155787289165246585583291819252627720144687822781808529370613377586610735928178283327207791931897883424633325083583001975227016830407188727609132036632946234419301131666389964830321414921172514131959586030586931111249491498106713817311838283034349524325163097453961907669495483388300826404610851466022463454212313603637565042757263073095191351465395578859789289286623320311957329723105215118350211185629815472005840341390060401666302409887985194198907321230384356718336469944222033952614808736700826052596589783073153308736029332962140644960168255815809288477363038352552111837655071019625450260503418732701804784747182324638570871601380717550522471539631880754137751840248666247067558719456661594013155374353565787812302603454241932587478074531723845881852522899875520108223989565161816290836725233062170653322013442338668982907977623671041502866086951618008336554936548381992485724315445742522418652645366236207797254801446299025033667397474972659524455906539862842231515555042136670038247248897838354864879530283890881209788864080366922898130228485869246412234498989357579422587192729993196385899640805525931849963321047376078696409505210382363852446788333692920589280728231042105259768204967935237630730947289546176237344157978687526209734663065396354369435887509555819496761529612670892267592613261368154786970843333205497696978891361396207152144495001501963211406214283549677114836227070689864106611003794440829922052585114742533372193737747468840053514452728905654108384095706621378519493931924415799771055333810098449370026530525687192051298576502186041804793590285571178492574358690394687483560097079894226196628064591511497281471180947997153327377330473027002482264767742036860570511304613104070588191520523721602975179515534689251675096747888297896189014738139384973413497771956407580089944032595700454254757322594723644055223823257936218414738084433738393480670154822354418285633492955295404766761380204585025501914177392046923017909349445763892709995098736896765635526774603125001 We create a new script called wolframalpha_script.py , remove the sol = sol % (10**10000) operation, remove the call to m_func, and paste in a call to decrypt_flag with the value obtained from WolframAlpha. Running wolframalpha_script.py prints the flag.
Slightly Less Cheesy Method
Note: This takes more time to understand than the above method, but you will learn more (but you still won't learn about matrix diagonalization, which was intended by the challenge authors).
We can solve this challenge using sympy's rsolve function and gmpy2's mpz . I initially tried to solve this challenge this way instead of using WolframAlpha, but I couldn't figure out rsolve. It turns out that instead of writing the function like this f = 55692*y(n-4) - 9549*y(n-3) + 301*y(n-2) + 21*y(n-1), it needs to be written like this f = -55692*y(n) + 9549*y(n+1) - 301*y(n+2) - 21*y(n+3) + y(n+4) due to how sympy's recurrence function was designed. Once we get the equation we need to rewrite it using gmpy2's mpz so it can be evaluated at 2e7 fast enough. According to the docs , "the gmpy2 mpz type supports arbitrary precision integers... [and] an mpz will be faster than Python's long once the precision exceeds 20 to 50 digits." The complete solution code is in solve.py . There are some other options that I discuss in the solve.py script comments, but they do not work as well.
Intended Method
The intended method writeup is not finished. This writeup discusses the intended matrix diagonalization method to find the function in standard form (in the above method we use sympy's rsolve function to accomplish this). That writeup then uses the same approach discussed above regarding the usage of gmpy2's mpz.
Using WolframAlpha we know that the general form of the recurrence relation is $a(n)=\frac{1612(-21)^n+306852^{2n+5}3^n-108282913^n+8349 17^{n+1}}{42636}$. This could have been caculated using matrix diagonalization (see this helpful pdf ). We need to calculate $a(n)\bmod 2*10^{10000}$. We can use the following properties to compute this efficiently:
$(a + b)\bmod m = ((a\bmod m) + (b\bmod m))\bmod m$
$(ab)\bmod m = ((a\bmod m)(b\bmod m))\bmod m$
$\frac{a}{b}\bmod m=(a*\frac{1}{b})\bmod m=((a\bmod m)(\frac{1}{b}\bmod m))\bmod m$
We can rewrite $a(n)\bmod m$ (where $m=2*10^{10000}$) using these properties:
$(((1612(-21)^n+306852^{2n+5}3^n-108282913^n+8349 17^{n+1})\bmod m)(\frac{1}{42636}\bmod m))\bmod m$ (by property 3)
$(((1612(-21)^n+306852^{2n+5}3^n-108282913^n+8349 17^{n+1})\bmod m)(\frac{1}{42636}))\bmod m$ (because $\frac{1}{42636}<m$)
$((((1612(-21)^n\bmod m)+(306852^{2n+5}3^n\bmod m)-(108282913^n\bmod m)+(8349 17^{n+1}\bmod m))\bmod m)(\frac{1}{42636}))\bmod m$ (by property 1)
$(((((1612\bmod m)((-21)^n\bmod m)\bmod m)+((30685\bmod m)(2^{2n+5}\bmod m) (3^n\bmod m)\bmod m)-((1082829\bmod m)(13^n\bmod m)\bmod m)+((8349\bmod m) (17^{n+1}\bmod m)\bmod m))\bmod m)(\frac{1}{42636}))\bmod m$ (by property 2)
So, the python function would be something like this:
Copy def m_func ( n ):
return ((((( 1612 % m) * ( pow ( - 21 , n, m) ) % m) + (( 30685 % m) * ( pow ( 2 , 2 * n + 5 , m) ) * ( pow ( 3 , n, m) ) % m) - (( 1082829 % m) * ( pow ( 13 ,n,m) ) % m) + (( 8349 % m) * ( pow ( 17 ,n + 1 ,m) ) % m)) % m) ((( 1 )) / ( 42636 )) ) % m Flag
picoCTF{b1g_numb3rs_afc4ce7f}
