Rating: 5.0

# Crunchy - 50 points - 73 solves

# Binary recurrence sequence modulo prime

We get a recurrence relation `x(n) = 6*x(n-1)+x(n-2)`, with `x(0)=0,x(1)=1`. The flag is `INSA{x(g)%p}` for a very large value of `g` and a prime `p`.

This challenge is trivial to solve using a module of sage I discovered: `sage.combinat.BinaryReccurenceSequence`. With this module we can easily find the period of `x` modulo `p`. Then we just need to reduce `g` modulo this period and we get the flag. Here is the solution script:

```python

p = 100000007

T = BinaryRecurrenceSequence(6,1)

period = T.period(p)

g = 17665922529512695488143524113273224470194093921285273353477875204196603230641896039854934719468650093602325707751568

trunc_g = g%period

print T(trunc_g)%p

```

which gives the flag `INSA{41322239}`.