Sequences picoCTF 2022 Solution

Description

1. Step 1Read the real recurrence from sequences.py

   Observation

   The description says the naive recursion never finishes. Read the script first for the exact coefficients, base cases, and target index, before optimizing anything.

   sequences.py defines a 4-term linear recurrence of the form M(i) = a*M(i-1) + b*M(i-2) + c*M(i-3) + d*M(i-4). The script uses coefficients 21, 301, -9549, 55692 (so M(i) = 21*M(i-1) + 301*M(i-2) - 9549*M(i-3) + 55692*M(i-4)), base cases 1, 2, 3, 4, and a target index of 20,000,000 (2 * 10^7). Confirm these by reading your downloaded sequences.py - copy the coefficients and the index verbatim, they are the only inputs the solution needs.

   Learn more

   A linear recurrence is a sequence where each term is a fixed linear combination of the previous terms. Fibonacci (f(n) = f(n-1) + f(n-2)) is the 2-term example. This challenge uses a 4-term recurrence with specific integer coefficients written directly in sequences.py.

   The author's recursion recomputes the four predecessors of every term independently, which is exponential: computing the 20-millionth term this way would take longer than the age of the universe. Memoization brings it down to O(n) time and O(n) space, but n = 2 * 10^7 still makes that impractically slow and memory-hungry in pure Python.

   There is no encryption anywhere in this challenge. The flag is simply the printed value of the recurrence at the target index, formatted as the script expects. The entire difficulty is computing that one number fast enough.

2. Step 2Compute the nth term with matrix exponentiation

   Observation

   The target index is around 20 million and the recurrence has exactly four terms. Encode the state as a 4x4 companion matrix and square-and-multiply, and the linear traversal becomes a logarithmic number of matrix multiplications.

   Encode the recurrence as a 4x4 companion matrix M acting on the state vector [M(i-1), M(i-2), M(i-3), M(i-4)]. Then [M(n), ...]^T = M^(n-3) * [M(3), M(2), M(1), M(0)]^T. Raise M to the power with fast exponentiation. Use Python integers (or gmpy2.mpz for speed) - these are exact integers, so keep full precision and do NOT reduce modulo anything unless sequences.py itself prints a modular result. An alternative is to diagonalize M (P * D^n * P^-1) and clear denominators with a single final division to avoid floating-point rounding; the integer matrix-power approach below sidesteps that issue entirely.

   python

   python3 -c "
   # Fill the coefficients, base cases, and index from sequences.py.
   # Example values shown; confirm them in sequences.py before running.
   # Recurrence: M(i) = c1*M(i-1) + c2*M(i-2) + c3*M(i-3) + c4*M(i-4)
   c1, c2, c3, c4 = 21, 301, -9549, 55692
   base = [3, 2, 1, 0]              # placeholder order; see note below
   init = [1, 2, 3, 4]             # M(0), M(1), M(2), M(3) from sequences.py
   N = 20_000_000                  # target index from sequences.py
   
   def mat_mul(A, B):
       n = len(A)
       C = [[0]*n for _ in range(n)]
       for i in range(n):
           for k in range(n):
               if A[i][k]:
                   aik = A[i][k]
                   row = B[k]
                   Ci = C[i]
                   for j in range(n):
                       Ci[j] += aik * row[j]
       return C
   
   def mat_pow(M, p):
       n = len(M)
       R = [[1 if i==j else 0 for j in range(n)] for i in range(n)]  # identity
       while p:
           if p & 1:
               R = mat_mul(R, M)
           M = mat_mul(M, M)
           p >>= 1
       return R
   
   # Companion matrix: state [M(i-1), M(i-2), M(i-3), M(i-4)] -> [M(i), ...]
   M = [
       [c1, c2, c3, c4],
       [1,  0,  0,  0],
       [0,  1,  0,  0],
       [0,  0,  1,  0],
   ]
   
   # State vector at i=3 is [M(3), M(2), M(1), M(0)]
   state = [init[3], init[2], init[1], init[0]]
   P = mat_pow(M, N - 3)
   val = sum(P[0][j] * state[j] for j in range(4))
   print('M(N) =', val)
   # Format exactly as sequences.py does to read the flag.
   "

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Replace the recursion with a memoized version using functools.lru_cache or a dictionary cache to store already-computed terms

   Memoization takes the call tree from exponential to linear, but n here is 20 million. In pure Python that is 20 million calls and a dictionary of 20 million entries, which exhausts memory and takes minutes. Matrix exponentiation finishes in a logarithmic number of multiplications, about 24 iterations, however large n gets.

   Tried: Add a 'mod 2**64' or similar modular reduction inside mat_mul to keep intermediate integers small and speed up the multiplication

   sequences.py prints the exact integer value of the term and formats that into the flag. Reduce modulo anything the script does not also reduce by and you end up with a residue rather than the true term, so the flag comes out wrong. Only apply a modulus if the script's own flag-printing line applies one.

   Learn more

   The key identity: the recurrence M(i) = c1*M(i-1) + c2*M(i-2) + c3*M(i-3) + c4*M(i-4) is a single linear map on the state vector. Stacking it gives [M(i), M(i-1), M(i-2), M(i-3)]^T = M * [M(i-1), M(i-2), M(i-3), M(i-4)]^T, where the first row of the 4x4 matrix holds the coefficients and the subdiagonal shifts the state down.

   By induction, applying the map n - 3 times from the base state gives the answer: state(n) = M^(n-3) * state(3). Computing M^(n-3) with square-and-multiply costs only O(4^3 * log n) integer multiplications, which is instant even for n = 2 * 10^7.

   Two implementation notes: (1) these are exact integers and they grow large, so use Python's arbitrary-precision ints (or gmpy2.mpz to speed up the big multiplications); (2) double-check the index convention in sequences.py (0-based vs 1-based, and exactly which term is requested) and adjust the N - 3 exponent and the starting state to match.

3. Step 3Format the computed value as the flag

   Observation

   The description says the flag is whatever the script prints, with no separate decryption. So the formatting logic is already in sequences.py, and the only step left is feeding the computed integer back through it.

   Once the matrix power finishes, sequences.py formats the computed term into the flag. Apply the exact formatting the script uses (string conversion / wrapping in picoCTF{...} as written in the file) and submit. There is no XOR, AES, or any other decryption - the flag is the number itself, formatted.

   Learn more

   The challenge tests one thing: knowing that linear recurrences reduce to matrix exponentiation (or matrix diagonalization), which collapses an intractable O(exp) or O(n) computation down to O(log n). The flag derivation is whatever printing/formatting sequences.py already contains - typically the integer value placed into the flag wrapper.

   Matrix exponentiation for linear recurrences is a staple of competitive programming and shows up across many CTF problems in disguise: Fibonacci variants, tiling counts, and path-counting in graphs all reduce to raising a transition matrix to a power. Recognizing the pattern is the transferable skill here.

Flag

The flag is the recurrence value at the target index (around the 20-millionth term), formatted exactly as sequences.py prints it. Compute it with matrix exponentiation (or matrix diagonalization) in O(log n) time. Read the exact coefficients, base cases, and index from your downloaded sequences.py. No decryption is involved.