Past exam of the analytic number theory and elliptic curves course of the University of Oxford / 2008 / B / 8

Fix $P$ and put $e_m=h_x(mP)-m^2{h}_x(P)$ for $m\ge 0$. Then $e_0=e_1=0$. Apply the given approximate parallelogram identity with its two arguments $mP$ and $P$. The quadratic terms cancel exactly, leavingSet $d_m=e_m-e_{m-1}$. Starting from $d_1=0$, the inequality gives $|d_m|\le (m-1)C$. Summing from one to $m$ therefore yieldsThus $C_m=m(m-1)C/2$ works independently of $P$, including $m=1$.

The preceding bound at $m=2$ gives $|h_x(2Q)-4h_x(Q)|\le C$ for every point $Q$. For $a_n=4^{-n}{h}_x(2^{n}P)$, take $Q=2^{n}P$ to obtainFor $m>n$, summing the geometric tail givesThus the sequence is Cauchy and converges by completeness of the real numbers. The estimate also gives a quantitative bound on its distance from the limit.

For prime-power contraction in a formal group, a one-dimensional formal group over $R$ has $F(X,Y)=X+Y+$ terms of total degree at least two with coefficients in $R$. Induction under composition therefore givesFor $|x|<1$ this converges and the non-Archimedean inequality gives $|[p](x)|\le \max (|p||x|,|x{|}^2)$. The residue characteristic implies $|p|<1$; in equal characteristic $p$ the linear coefficient is zero, which only improves the bound.

Let $x_n=[p^n](x)$, so $x_{n+1}=[p](x_n)$. If $x=0$ there is nothing to prove. Otherwise put $\rho =\max (|p|,|x|)<1$. Inductively $|x_n|\le |x|$, and then $|x_{n+1}|\le \rho |x_n|$. ThusCompleteness ensures convergence of the formal-series evaluations. The contraction argument in fact does not need the extra discreteness assumption.

For prescribing a factor by elliptic-curve tripling, quadratic reciprocity gives $(3/p)=1$ when $p\equiv 1(\mathrm{mod}12)$. Choose $r\in {\mathbb{F}}_p$ with $r^2=3$ and choose an integer $a$ by the Chinese remainder theorem so thatThen $a^2+6a-3\equiv 0(\mathrm{mod}p)$ and it is four modulo $q$.

The curve $E:y^2=x^3+ax-a$ has discriminant $-16a^2(4a+27)$. At $p$, $a\ne 0$, since otherwise $r=3/2$ would force $p=3$. Also $4a+27=15+8r$ cannot vanish: squaring $8r=-15$ would give $192=225(\mathrm{mod}p)$, forcing $p=3$ or 11, neither in the required class. At $q$, $a=1$ makes $a(4a+27)=31$, and $q\equiv 5(\mathrm{mod}12)$ excludes $q=31$. Thus both reductions are nonsingular.

The point $P=(1,1)$ is on every curve in this family. Doubling it uses the invertible denominator two and givesModulo $p$ this difference vanishes, and the doubling ordinate is $-1$, so $2P=-P$ and $3P$ is the identity. Modulo $q$, taking $a=1$ gives $x(2P)=2$, so $2P$ and $P$ have distinct abscissas and their sum is a finite point.

Consequently the attempted addition computing $3P$ modulo $N$ asks to invert a denominator divisible by $p$ and not by $q$. Its numerator is nonzero modulo $p$, since the two ordinates there are minus one and one, so this is not a removable coincidence. The Euclidean gcd used for inversion returnsa proper factor. Thus the specified elliptic-curve computation successfully factors $N$.