CrewCTF 2025 PPC Writeup

ABC conjecture

Problem Statement

Given a triplet $(a,b,c)$, produce polynomials $A,B,C$ over $GF_p$ such that:

• The number of distinct roots of $A$ is $a$
• The number of distinct roots of $B$ is $b$
• The number of distinct roots of $C$ is $c$

Additionally, require that $A + B = C$.

Among all solutions, find one that minimizes the maximum degree among $A,B,C$.

Assume $0 \le a,b,c < 10$, and $p \sim 2^{256}$.

Initial Analysis

This is equivalent to finding $A + B + C = 0$, and without loss of generality we can assume $a \le b \le c$.

Since $C$ has $c$ distinct roots, $\deg C \ge c$. Therefore, the minimized maximum degree over $A,B,C$ is at least $c$.

Since $p$ is very large, a random degree-$n$ polynomial is irreducible with probability about $\frac{1}{n}$, and splits completely (has $n$ distinct roots) with probability about $\frac{1}{n!}$.

Thus, our use of randomness should rely on irreducibility rather than on forcing $n$ distinct roots.

To make a degree-$n$ polynomial have fewer than $n$ distinct roots, we have two strategies:

• Collide roots (e.g., use repeated linear factors)
• Make it divisible by an irreducible factor of degree > 1

If we explicitly construct the polynomial, the first approach is convenient. If we generate polynomials randomly, the second is more practical.

Solution for Some Cases

If $a=0$ and $c \ge 2$, we can do the following:

Pick distinct $z_1,\dots,z_c$, and set $C = \prod_{i=1}^{c} (x - z_i)$, which has $c$ distinct roots.

Pick distinct $y_1,\dots,y_b$, and set $B = \prod_{i=1}^{b} (x - y_i)$, which has $b$ distinct roots.

Let $A = -B - C$. If $A$ is irreducible, we have a valid solution for $(a,b,c)$. Otherwise, repeat.

Here $A$ should behave similarly to a random polynomial, so this succeeds with probability on the order of $1/c$.

General Solution

If $a \ge 1$, pick a random $t$, recursively solve the sub-instance $(a-1,b-1,c-1)$ to obtain $A',B',C'$, and then return $A=A'(x-t)$, $B=B'(x-t)$, $C=C'(x-t)$.

There are three remaining cases with $c \le 1$:

• $(a,b,c) = (0,0,0)$: take $A=1$, $B=2$, $C=-3$.
• $(a,b,c) = (0,1,1)$: take $A=1$, $B=x+1$, $C=-x-2$.
• $(a,b,c) = (0,0,1)$:
  • This is the only case where we can't fit $A,B,C$ with maximum degree $c$.
  • If we allow degree-2, we can randomly generate $C = (x - z_1)^2$, then try to find irreducible $A,B$ with $A + B = C$.

Finally, since $(a,b,c) = (0,0,1)$ does not yield a solution with maximum degree equal to $c$, we must also handle $(a,b,c) = (1,1,2)$ specially. One approach: set $A=(x-x_1)^2$, $B=(x-y_1)$, and check whether $-A-B$ has two distinct roots.

Code

from pwn import *
from sage.all import *
from functools import lru_cache

context.log_level = 'debug'
r = remote('abc-conjecture.chal.crewc.tf', 1337, ssl=True)

r.recvuntil(b'p=')
p = int(r.recvline().strip().decode())

print(f"{p=}")
F = GF(p)
R = F['x']
x = R.gen()


@lru_cache()
def solve2(a, b, c):
    if not (a <= b <= c):
        if a > b:
            B, A, C = solve2(b, a, c)
        else:
            A, C, B = solve2(a, c, b)
        return A, B, C

    if (a, b, c) == (1, 1, 2):
        while True:
            A = (x - randint(0, p - 1))**2
            B = (x - randint(0, p - 1))
            C = -A - B
            if len(C.roots()) == 2:
                return A, B, C
    if (a, b, c) == (0, 0, 1):
        while True:
            C = (x - randint(0, p - 1))**2
            A = R.irreducible_element(2)
            B = -A - C
            if B.is_irreducible():
                return A, B, C
    if (a, b, c) == (0, 1, 1):
        return R(1), R(x + 1), R(-x - 2)
    if (a, b, c) == (0, 0, 0):
        return R(1), R(2), R(-3)

    if a >= 1:
        t = randint(0, p - 1)
        A, B, C = solve2(a - 1, b - 1, c - 1)
        return A * (x - t), B * (x - t), C * (x - t)

    while True:
        C = R(1)
        for _ in range(c):
            C *= x - randint(0, p - 1)
        B = R(1)
        for _ in range(b):
            B *= x - randint(0, p - 1)
        A = -C - B
        if A.is_irreducible():
            return A, B, C


def solve(a, b, c):
    A, B, C = solve2(a, b, c)
    return A, B, -C


while True:
    r.recvuntil(b'Give me your solution for')
    a, b, c = map(int, r.recvline().strip().decode().split(', '))
    A, B, C = solve(a, b, c)
    r.sendline(','.join(map(str, A.list())).encode())
    r.sendline(','.join(map(str, B.list())).encode())
    r.sendline(','.join(map(str, C.list())).encode())

rotating subsequence

Problem Statement

Given numbers $N,K$ with $N \sim 2^{256}$ and $3 \le K \le 102$.

For a sequence $A = a_1,a_2,\dots,a_x$, a non-empty subsequence specified by indices $b_1,\dots,b_y$ is called rotating if:

• $a_{b_{i+1}} \equiv a_{b_i} + 1 \pmod{K}$ for all $i = 1,2,\dots,y-1$, and
• $b_i < b_{i+1}$ (indices strictly increase).

Note: $y$ may be 1. Indices matter.

Given $N,K$, construct a sequence $S$ such that $S$ has exactly $N$ rotating subsequences, with the additional constraint that the length of $S$ is at most $256 \cdot K$.

Algorithm for Computing Solutions

Let the sequence be $s_{1..m}$.

Let $f_{i,j}$ be the number of rotating subsequences with last index $\le i$ and last value equal to $j$.

Then for most $j$, $f_{i,j} = f_{i-1,j}$, while $f_{i,a_i} = f_{i-1,a_i} + 1 + f_{i-1,(a_i - 1) \bmod K}$.

The final count is $\sum_{j=0}^{K-1} f_{m,j}$.

def calc(s, k):
    f = [0] * k
    for x in s:
        f[x] += 1 + f[(x - 1) % k]
    return sum(f)

Observing Properties

What is the simplest case? Smaller $K$ should be easier, so consider $K = 2$ (and we’ll soon see why it was excluded).

When $K=2$, $f$ has two components; denote it by $(x,y)$.

When a new element arrives, $(x,y)$ becomes either $(x,x+y+1)$ or $(x+y+1,y)$. Initially it is $(0,0)$.

Let $a = x + 1$, $b = y + 1$. Then the transition becomes $(a,b) \to (a,a+b)$ or $(a+b,a)$.

This shows a necessary condition for a pair $(a,b)$ to be reachable is $\gcd(a,b) = 1$.

It is also sufficient: the subtraction-based Euclidean algorithm applied to any $(a,b)$ will lead to $(1,1)$, and this is essentially the unique reverse path.

Algorithm for K=2

Given $N$, find $a,b$ such that $a + b = N + 2$ and $\gcd(a,b)=1$, then reconstruct the sequence via the subtraction-based Euclidean algorithm.

But which partition $(a,b)$ is optimal? Alternatively: if we want to reach large $(a,b)$ with as few steps as possible, what do optimal pairs look like?

Repeatedly applying $(a,b) \to (a,a+b) \to (2a+b,a+b)$ yields Fibonacci-like growth, i.e., $(\text{fib}_{n},\text{fib}_{n+1})$.

We can hypothesize that the best choice satisfies $a \approx \varphi b$, where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio.

Here is a script that follows this intuition:

from decimal import *
from math import gcd
import random


def compute_golden_ratio():
    sqrt_5 = Decimal(5).sqrt()
    phi = (sqrt_5 - Decimal(1)) / Decimal(2)
    return phi


getcontext().prec = 500
phi = compute_golden_ratio()


def golden_round(x):
    x_dec = Decimal(str(x))
    result = x_dec * phi
    return int(result)


def solve2(n):
    t = n + 2
    a = golden_round(t)
    while gcd(a, t) != 1:
        a += 1
    b = t - a
    s = []
    while a > 1 or b > 1:
        if a > b:
            a -= b
            s.append(0)
        else:
            b -= a
            s.append(1)
    print(a, b, len(s))
    return s[::-1]


def calc(s, k):
    f = [0] * k
    for x in s:
        f[x] += 1 + f[(x - 1)) % k]
    return sum(f)


n = random.randint(0, 2**256)
assert calc(solve2(n), 2) == n

While this finds a solution for $N$, it rarely fits the length bound of $256 \cdot 2$.

It performs much better than choosing a random partition (e.g., replace a=golden_round(t) with a=random.randint(1,n)), but it is still too long in many cases.

In fact, the minimal sequence length for given $N$ is described by OEIS A178047, which is hard to optimize against directly. This likely explains why $K=2$ is excluded in the challenge.

Generalization to K=3

Similarly, write $f_i + 1$ as a triple $(a,b,c)$. Each step transforms it to one of:

• $(a, b + a, c)$
• $(a, b, c + b)$
• $(a + c, b, c)$

It can be shown that $\gcd(a,b,c)=1$ is necessary and sufficient.

A natural guess is that the cyclic sequence $[0,1,2,0,1,2,\dots]$ maximizes the growth rate of $N$. The limiting ratio $\frac{b}{a}$ or $\frac{c}{b}$ tends to the supergolden ratio $\psi$.

Thus, we can partition $N + 3 = a + b + c$ with $\gcd(a,b,c)=1$ and target $b \approx \psi a$, $c \approx \psi b$.

However, we now have multiple possible reverse moves: e.g., $(a,b,c) \to (a,b-a,c)$ or $(a,b,c-b)$. Which is better?

Heuristic:

• Let the minimum among $(a,b,c)$ be $a$ (otherwise rotate).
• Define a score for $(a,b,c)$ as $\left|\psi - \frac{b}{a}\right| + \left|\psi - \frac{c}{b}\right|$, the “distance” to the ideal proportions $(x, x\psi, x\psi^2)$.
• Whenever multiple moves are available, choose the one that minimizes this score.

Generalization to larger K

For larger $K$, $\gcd(f_i + 1) = 1$ remains necessary and sufficient.

There is also a limiting ratio for successive components $\frac{f_{i+1}}{f_i}$.

However, when choosing the next reverse step, there are up to $K-1$ options. We need to optimize the selection efficiently.

Code

from math import gcd
import random

C = 512


def gcdall(s):
    g = s[0]
    for i in range(1, len(s)):
        g = gcd(g, s[i])
        if g == 1:
            return 1
    return g


class Solver:
    def __init__(self, k):
        self.r = random.Random(123)
        self.k = k

        # Approximate the growth ratios by iterating k*C steps
        a = [1] * k
        for i in range(k * C):
            a[i % k] += a[(i - 1) % k]
        self.a = a
        self.sa = sum(a)
        self.fr = (a[-1] << C) // a[-2]

    def solve(self, n):
        n += self.k
        p = [n * x // self.sa for x in self.a]
        for _ in range(n - sum(p)):
            p[self.r.randint(0, self.k - 1)] += 1

        while gcdall(p) != 1:
            p[self.r.randint(0, self.k - 1)] += 1
            p[self.r.randint(0, self.k - 1)] -= 1
        assert sum(p) == n

        # f stores the per-edge “distance” terms
        f = [0] * self.k
        for i in range(self.k - 1):
            f[i] = abs((p[i] << C) // p[i + 1] - self.fr)
        fsum = sum(f)
        pmin = (p[0], 0)

        # Compute change in fsum if we replace p[ci] with civ and track new minimum
        def fsumdelta(i, ci, civ, npmin):
            res = -f[i]
            if (i + 1) % self.k == npmin[1]:
                return res
            i1 = (i + 1) % self.k
            a = civ if i == ci else p[i]
            b = civ if i1 == ci else p[i1]
            return res + abs((a << C) // b - self.fr)

        res = []
        while max(p) > 1:
            best = None
            for i in range(self.k):
                i1 = (i + 1) % self.k
                if p[i] < p[i1]:
                    t = p[i1] - p[i]
                    npmin = pmin if t >= pmin[0] else (t, i1)
                    dset = {i, i1}
                    if t < pmin[0]:
                        dset.add((pmin[1] - 1) % self.k)
                    deltal = {x: fsumdelta(x, i1, t, npmin) for x in dset}
                    delta = sum(deltal.values())
                    if best is None or delta < best[0]:
                        best = (delta, i, i1, t, npmin, deltal)
            fsum += best[0]
            res.append(best[1])
            p[best[2]] = best[3]
            pmin = best[4]
            for x, y in best[5].items():
                f[x] += y
        print(len(res))
        return res[::-1]


if __name__ == '__main__':
    from pwn import *
    solvers = {}
    for i in range(3, 103):
        solvers[i] = Solver(i)
    context.log_level = 'debug'
    r = remote('rotating-subsequence.chal.crewc.tf', 1337, ssl=True)
    for _ in range(50):
        r.recvuntil(b'N=')
        n = int(r.recvline().strip().decode())
        r.recvuntil(b'K=')
        k = int(r.recvline().strip().decode())
        s = solvers[k].solve(n)
        r.sendline(','.join(map(str, s)).encode())
    r.interactive()

日期： 2025-09-22

标签： CTF Writeup