# Sequences

## 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](https://github.com/HHousen/PicoCTF-2022/blob/master/Cryptography/Sequences/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}`](https://www.wolframalpha.com/input?i=a%280%29%3D1%2Ca%281%29%3D2%2Ca%282%29%3D3%2Ca%283%29%3D4%2Ca_n%3D55692a_%7Bn-4%7D+-+9549a_%7Bn-3%7D+%2B+301a_%7Bn-2%7D+%2B+21a_%7Bn-1%7D). Running this produces $a(n)=\frac{1612(-21)^n+30685*2^{2n+5}3^n-108282913^n+8349*17^{n+1}}{42636}$. Now, we need to find the last 10,000 digits of $a(2*10^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`](https://www.wolframalpha.com/input?i=%281612+%28-21%29%5En+%2B+30685+2%5E%285+%2B+2+n%29+3%5En+-+1082829+13%5En+%2B+8349+17%5E%281+%2B+n%29%29%2F42636+mod+10%5E10000+when+n%3D2e7). This query outputs the following 10,000 digit integer:

```
9255992309255409483179419845385604076174038906804435862147131271801573863364671050296589603656758794258408363769683958014335858678927280224225587045835554549236411759910608220745411090061107428308955685273979287406544038776309083120692585385738829595466109925134108641705991448085508655504450017990509268760925633701568972881830027061610560435878782702300627297929494871966955716917939371706707268015616593308156496696604916581937050769400369329646318242403439293960972797326591961508734072823394003350315417131956614413828716990680272404638311428692240287388862893111312382911200690775170712470656181173871770843346165473902020842788371815280837350600345873274612288695974628974447382548367670699187634577856102734888566085413732796006178277409299011898018586005894168842976151756634127393139021619117795598661633051521271539523878676739785948001294884571789689490927900913683983739549130273396058399143226419007679327244720322508238328094638668628927305146465933124499123166025607367183896479143811606663266607998143104781472932536517962870064142946144625397409118482948529375842470080996308940228181555868856278635118907503183008759948969042642499296992802929823117992152968592210773980077617609073992433539666043450153737078290684650605359729295102951770694711461980246093793230726069510952832108390343839058578187834443332785573981574093142883050492227667587060213520259865514144542328249027296100425783797607012578290271918793953435463360127600336995858457256850614392061752272722254154308105713290184809674001961254146687993990619053173026936872310492713720330275500652722252195618029796316172978100805935132221268612041959579928042577530526820419119584535052685904447261275310418413248686956899719552564514439618702687638343849484513674694171734435213591420260740566479490794343621991808171166760491608939159807834320688115459926363623951639944589028697445192690646124728566256342389792435969804521066155975776703867010670866905226643086877863465230710100595718033849129799770334210438392357318197622026595775013560170000581836767441557468287425384470655606044094877141189131911510528837751403182546932730981726862216771989383509234877567054461236826949390614566495105022255382856931991575044242339913426032792306478049565359457186829132169808003222243325028652626310095161166749383960092203262812957052229181656830263059054012215047216588117847290728018790343673230003332953508551258024784915192282602155534492742678877926631791253048827739564711644506014349266360429184321481406973201467494658627340758651248713537093402837529826098026053980059834955577271342991416289835227752675490374970512450046682049106507080363044373334490863015296351867206843957520897668462624524697408794293584230426162185084180656752348354284781732407856125955024240750800619775537915436516642312543485650255028594050775824329726464411065155974834914382223375359322586073472902099799870968399129353093933551117138823131500391523207862454881095643216836059114056185567621210349969346322773001970523136569586467928553922556759816995780147911338014075002398099900406865475250060061466196595711092783115852233928711362221294428465110008730032376221811390098890201357718636406741505189198093628817125780661479980043085639258408363072938360753891009465462833335469632467626044690421375033291457334660505739506576025799178496006189196177956994530824690940218609585303782913911708447438142187182926981478894626795456902176806611295290700707265838620112296859471410916725995917774332274290788363516703126067525815657749686032894240952885372190041514195745517242466094437249645852862039820489243179115296739411857999937345382824004834661340869046052653646306780119433815387152755133605774561035882025757872567705036320478601722273548057596707229169819752947743173434922514692459604659989254924691025826519889997310022991556840695569039726702142704241050410911435207616994113021032464407922133128294008095361971182034734357545845729036366311342093217648851382217300855617348105944416959797800045679106051418970936740212201243323374420621407825691038198850295142424362386735016850455273108385213347814948477424622972677362919476397615254720546530031804494636576667039213835518167079053755689483780169794708659175854750079429248450088295652150342673865847877948007025066365086867044327664549023605585607043999489198176552411509573614509346696314655265681005379692562018978024392184039921374721689942446250899039972858579928731641819612416834076914289563149490277258128048991899111474196559739496407766224802408886023880978692457886403296980175876160991944550852846912763591834524913193729446086608083228520607915228071996267423308343063134888427907517509315007222472389958749971119851036755792600655325528041204067006759701899650882688051833189752046173730379687971618778106152429359138121583193895560513945636243134471509560159959342910138282307726776095970363559666437861045509504138185181506053793512330290527298473960426572845110238171117683684041364809195193134404789631117855182678689233515561942021072691997136439472830027014623367190862026964245957075271549021475940633067620735535147002394377565757136258368893655670057033255721591133344504950327269570084772598756931676545313429328183852664697498916280009082153424970243321291245567462087352044270433243592074410354599395985297648098973502854925696106939367723393764563272258573159869455233248604794095580403785375164969409403081664991958224758441901558161776076591761888047641751838451040113125346830296747468600274844343324792391841427920168269451466724402733360927693709608962574594464579536984204944785654570365966337092840214689194020777824352704334046313881288338804180775802282603846332149028417773288289252762349196418160264959236996771411726564554602445482384874934737046588338703536104981717946192703044019694658564450098648845491774640036585262302060685132707254404537015003307098121867501852580890489939024131889401235319636551040339975967238422740240966259515037478254770473708996730051186960847990806128716407679744434499599989634137262723021472296892338440434736145378291606947957568823870560743760517351104324171646786563571781160467327443314778456838020015351241446028925489659469259191936419394977586960658145019513424973791091137643248921605946312129559765684939065366382416571402819258368193526542981160896431303284342924396162774222454806500316599596574249681068946095848501619763049813933785364480427016321396723833776401301274077949645225141713635020427987198026380348105434595680144888649570836956452691173177645938260028423349017079649855941675840603611580622678506371371697560589581420055017577346354260361897276945627730859540343204410331899938007511401885662258331200755215828320367067692873598022854726551625019874259353828693391050015840864024895999795407357598143936695574892246307842161783795560397647511274081780556477771717482679637977149078124055360544607647924994542360536953444119017948371483912417341760402319880478433679698847402873629477418088386984882884367030602730629280761454042804309591833135472741106210177450590122900331916392690960166575957302364880258370864660313841070468917976423612480270717152957780709455158756388635972782046126933529379819689066556155764477143246285455968257184500627209798685519518396787028389456612015798784443980456558550117443763642092453428667889633895366126970127595278029054151815294466903598493508152766946482827975630302463357183665021121093456732176958408682571069411703078859156168396080558652545622296864811704928778418723691428995865934077090633785666707553168035257181052413086259223364488253377812633572773449366795144005798862081976863438611157642682042555702811274364249588365217230773276938197025251263204920250274561918739940317025820821943112146326658971603405997249518942370887739428430647434654176831358048833125278711592425215074394781203447864697270631159656012070957627193840233040056721098784067686855982514452154301379396013592845015085700333286408687000310352955163502073542407384258224528062051710025286474577927921058848236668349074255824260841594925768567573318340711331715155787289165246585583291819252627720144687822781808529370613377586610735928178283327207791931897883424633325083583001975227016830407188727609132036632946234419301131666389964830321414921172514131959586030586931111249491498106713817311838283034349524325163097453961907669495483388300826404610851466022463454212313603637565042757263073095191351465395578859789289286623320311957329723105215118350211185629815472005840341390060401666302409887985194198907321230384356718336469944222033952614808736700826052596589783073153308736029332962140644960168255815809288477363038352552111837655071019625450260503418732701804784747182324638570871601380717550522471539631880754137751840248666247067558719456661594013155374353565787812302603454241932587478074531723845881852522899875520108223989565161816290836725233062170653322013442338668982907977623671041502866086951618008336554936548381992485724315445742522418652645366236207797254801446299025033667397474972659524455906539862842231515555042136670038247248897838354864879530283890881209788864080366922898130228485869246412234498989357579422587192729993196385899640805525931849963321047376078696409505210382363852446788333692920589280728231042105259768204967935237630730947289546176237344157978687526209734663065396354369435887509555819496761529612670892267592613261368154786970843333205497696978891361396207152144495001501963211406214283549677114836227070689864106611003794440829922052585114742533372193737747468840053514452728905654108384095706621378519493931924415799771055333810098449370026530525687192051298576502186041804793590285571178492574358690394687483560097079894226196628064591511497281471180947997153327377330473027002482264767742036860570511304613104070588191520523721602975179515534689251675096747888297896189014738139384973413497771956407580089944032595700454254757322594723644055223823257936218414738084433738393480670154822354418285633492955295404766761380204585025501914177392046923017909349445763892709995098736896765635526774603125001
```

We create a new script called [wolframalpha\_script.py](https://github.com/HHousen/PicoCTF-2022/blob/master/Cryptography/Sequences/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](https://github.com/HHousen/PicoCTF-2022/blob/master/Cryptography/Sequences/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](https://docs.sympy.org/latest/modules/solvers/solvers.html#sympy.solvers.recurr.rsolve) and [gmpy2's `mpz`](https://gmpy2.readthedocs.io/en/latest/mpz.html). 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](https://gmpy2.readthedocs.io/en/latest/mpz.html), "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](https://github.com/HHousen/PicoCTF-2022/blob/master/Cryptography/Sequences/solve.py). There are some other options that I discuss in the [solve.py](https://github.com/HHousen/PicoCTF-2022/blob/master/Cryptography/Sequences/solve.py) script comments, but they do not work as well.

### Intended Method

The intended method writeup is not finished. [This writeup](https://www.nullhardware.com/reference/hacking-101/picoctf-2022-greatest-hits/sequences/) 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+30685*2^{2n+5}3^n-108282913^n+8349*17^{n+1}}{42636}$. This could have been caculated using matrix diagonalization (see [this helpful pdf](https://www.math.ucla.edu/~soukup/Exposition/Linear%20Recurrence%20Relations.pdf)). We need to calculate $a(n)\bmod 2\*10^{10000}$. We can use the following properties to compute this efficiently:

1. $(a + b)\bmod m = ((a\bmod m) + (b\bmod m))\bmod m$
2. $(ab)\bmod m = ((a\bmod m)(b\bmod m))\bmod m$
3. $\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:

1. $(((1612(-21)^n+30685*2^{2n+5}3^n-108282913^n+8349*17^{n+1})\bmod m)(\frac{1}{42636}\bmod m))\bmod m$ (by property 3)
2. $(((1612(-21)^n+30685*2^{2n+5}3^n-108282913^n+8349*17^{n+1})\bmod m)(\frac{1}{42636}))\bmod m$ (because $\frac{1}{42636}\<m$)
3. $((((1612(-21)^n\bmod m)+(30685*2^{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)
4. $(((((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:

```python
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}`