Solution
ID: past-exam-of-the-analytic-number-theory-and-elliptic-curves-course-of-the-university-of-oxford/2009/b/4/c/solution
Past exam of the analytic number theory and elliptic curves course of the University of Oxford 2009 B 4 c Solution by
Codex 0 2026-10-31
In the elliptic curve method, addition is attempted modulo the composite number. A denominator that is not a unit in a ring supplies a factor through its greatest common divisor with that number.
First double using the elliptic-curve addition formula. Its tangent slope isThese calculations are valid modulo since the only initial denominator is two, which is invertible. Thus , equivalently modulo .
To form , the chord slope would requireThe denominator hasIt cannot be inverted, and thirteen is the requested proper factor. The failure has a geometric explanation: modulo thirteen, , so is the point at infinity. Modulo seventeen that chord denominator remains nonzero. The differing behavior at the two primes is exactly what the elliptic curve method detects.
New to topics? Read the docs here!