% MARKS ALLOCATED AS FOLLOWS:
% 1: 20. 2: 20. 3: 30. 4: 30. Total: 100.
% In more detail:
% 1: 20. 2: 20. 3: each part 10. 4: 30.
% By the way, delete 3(c) (and soln). Refer them also to exams qn. 6.
% Also, refer them after 4 to exams qn. 7.
% Possible qn 6 for the future: y^2 = x*(x^2 + x + 7)?
\input amssym.def
\input amssym.tex
%\def\Bbb{\bf}
\nopagenumbers
\magnification=\magstep1
%\hoffset=1truecm
%\voffset=2truecm
\baselineskip = 5.2 true mm
\font\frkkk=eufm10
\font\twelverm=cmr12
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\ninebf=cmbx9
\font\eightrm=cmr8
\font\sevrm=cmr7
\font\sixrm=cmr6
\font\scrpp=eusm10
\font\frkk=eufm10
\font\deffont=cmssi10
\font\chaptitle=cmbx10 at 14 pt
\tolerance=10000
\def\sqr{\ifmmode\square\else{$\square$}\fi}
\def\square{\vcenter{
\hrule height.1mm
\hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
\hrule height.1mm}}                  % This is a slimmer sqr.
\null
\def\le{\leqslant}
\def\ge{\geqslant}
\def\etq{{\cal E}_{\lower 1pt\hbox{\eightrm tors}}({\Bbb Q})}
\def\etqp{{\cal E}_{\lower 1pt\hbox{\eightrm tors}}({\Bbb Q}_p)}
\def\c{{\cal C}}
\def\d{{\cal D}}
\def\e{{\cal E}}
\def\pk{\phi _\kappa}
\def\im{{\hbox{\sl im}}}
\def\hs{H_{\varsigma}}
\def\hpk{\hat \phi _\kappa}
\font\sc=cmssqi8
\def\scc#1{\hbox{\sc #1}}
\def\sf{{\scc F}}
\def\pnbq{{\Bbb P}^n(\overline {\Bbb Q} )}
\def\hk{{\hat \kappa}}
\def\bq{{\overline {\Bbb Q}}}
\def\hq{{\hat q}}
\def\pv{\prod\limits_v }
\def\pnk{{\Bbb P}^n(K)}
\def\mnkvw{{\Bbb M}^n(K[{\bf v}^2,{\bf w}^2])}
\def\pnkv{{\Bbb P}^n(K[{\bf v}^2])}
\def\kj{\kappa (J)}
\def \qmods {{\Bbb Q}^*/({\Bbb Q}^*)^2}
\def \qmodss { {\Bbb Q}^*/({\Bbb Q}^*)^2 \times
{\Bbb Q}^*/({\Bbb Q}^*)^2 }
\def \qs{{\Bbb Q}^*}
\def \qss{({\Bbb Q}^*)^2}
\def\bbQ{\Bbb Q}
\def\bbF{\Bbb F}
\def\bbZ{\Bbb Z}
\def\bbR{\Bbb R}
\def\bbC{\Bbb C}
\def\notdiv{{\not\hskip-.5pt |\ }}
\def\Q{{\Bbb Q}}
\def\F{{\Bbb F}}
\def\Z{{\Bbb Z}}
\def\R{{\Bbb R}}
\def\C{{\Bbb C}}
%
\chaptitle
\noindent
\centerline{Elliptic Curves. Sheet 7. To be handed in during 8th Week.}
\rm
\bigskip
\noindent
{\bf 1.} Find the ranks of the
following elliptic curves.
\par\noindent {\bf (a).} $Y^2 = X(X^2 + 2X + 3)$.
\par\noindent {\bf (b).} $Y^2 = X(X^2 + 14X + 1)$.
%%\par\noindent {\bf (a).} $Y^2 = X(X^2 + 3X + 5)$.
%\par\noindent {\bf (a).} $Y^2 = X(X^2 + 5X - 5)$.
%\par\noindent {\bf (b).} $Y^2 = X(X^2 + 14X + 1)$.
%\par\noindent {\bf (c).} $Y^2 = X(X^2 + 2X + 3)$.
%%\par\noindent {\bf (d).} $Y^2 = X(X^2 + 2X + 9)$.  
%%\par\noindent {\bf (e).} $Y^2 = X(X^2 + 9X - 1)$.    
%%\par\noindent {\bf (f).} $Y^2 = X(X-12)(X-36)$. 
\medskip\noindent {\bf 2.}
Let $A,+$ be an Abelian group.
Let $h : A \rightarrow \R_{\ge 0}$ satisfy:
\par\noindent \ \ \ \ (I) There exists a constant~$C$, 
independent of~$P,Q$, such that
\par \ \ \ \ $ | h(P+Q) + h(P-Q) - 2 h(P) - 2 h(Q) | \le C $, 
for all $P,Q \in A$,
\par\noindent \ \ \ \ (II) For any~$B\in\R$, 
the set $\{P\in A:h(P)\le B\}$ is finite.
\par\noindent Show that~$h$ is a height function on~$A$. 
Show also that there exists 
a constant~$C_3$, independent of~$P$, such that $|h(3P) - 9 h(P)|\le C_3$, 
for all $P \in A$. 
\par [$\R_{\ge 0}$ denotes $\{ x\in\R : x \ge 0\}$].
\medskip\noindent {\bf 3.}
A four-letter word $L_1L_2L_3L_4$ has been divided
into two pairs: $L_1L_2$ and $L_3L_4$.
Each of these pairs has been converted
into an integer (of at most 4 digits)
via the standard map: $A \mapsto 01 , B \mapsto 02, \ldots ,
Z \mapsto 26$. These integers have been encoded by taking each to the
power of $d=4085$, modulo $N=10481$. The encoded message reads:
$$ 6012,\, 3236.$$ 
\noindent You may assume that $N$ is the product of two primes. 
You should show, in your calculations, how you are only using
numbers of length at most~$9$ digits.
\par\noindent
{\bf (a)} Find a proper factor of~$N$ (that is, a factor~$d$
of~$N$ satisfying~$1 < d < N$) by 
applying Pollard's ``$p-1$'' method,
using base~$2$ and exponent~$46$.
\par\noindent
{\bf (b)} Factorise $N$ by applying the Elliptic Curve Method,
using the curve $\e : Y^2 = X^3 - X + 1$ and~$3P$, where~$P=(5,11)$.
\par\noindent
{\bf (c)} Use the factorisation of~$N$ to decode the message
(which is the name of the town famous for being the country
music capital of New Zealand).
%\medskip\noindent {\bf 4.} A 16-letter message (including any spaces)
%has been split into 8 pairs
%of letters. Each pair of letters has been encoded into 4 digits,
%using the usual map $A\rightarrow 01,\ldots ,Z\rightarrow 26$
%and $\hbox{space}\rightarrow 00$. Each of these 4-digit blocks
%has been further encoded using the map $X \rightarrow X^d$~(mod~$N$),
%where $d=4903$, $N=8777$, resulting in:
%\par
%$4195\vert 7645\vert 1876\vert 3549\vert 7864\vert 3057\vert 72\vert 3654$.
%\par\noindent Working mod~$N$, find the multiple $k\cdot P$
%on ${\cal E}:Y^2=X^3 + X - 1$, where $P=(1,1)$ and
%$k=2^6\cdot 3^4 \cdot 5$ (explain the way
%that you have efficiently computed $k\cdot P$). Use this to factor~$N$
%(you may assume that $N$ is the product of two primes). Also, factor
%$N$ using Pollard's $p-1$ method, using base~$2$.
%Use the factorisation of~$N$ to deduce the decoding exponent~$e$
%such that $X \rightarrow X^e$~(mod~$N$) reverses the map
%$X\rightarrow X^d$~(mod~$N$). Hence decode the message. You should
%show in your working how you have done all of the above
%computations using only an eight-digit calculator.
\medskip
\hrule
%\bigskip
\bigskip
\bigskip
\bigskip
\centerline{\bf A Few Pieces of Computational Advice}
%\par
%I have the impression that some of you are making
%cryptography questions unduly time-consuming, due to
%very slow calculator methods for performing some of the
%basic steps. 
\medskip
\sevrm
\baselineskip = 3.4 true mm
If you want to perform something like: 2046 $\cdot$ 8018 mod~8777
on a pocket calculator, then the fast way is as follows. 
First, 2046 $\cdot$ 8018 = 16404828. Now divide by 8777
to get the decimal~1869.070069; now subtract off the integer
part 1869 to get .070069; now multiply by 8777 to
get the decimal 614.99561; this is guaranteed to be almost
exactly an integer, and the nearest integer (namely: 615) will 
be 16404828 mod~8777. If you want to check it 
be 100\% sure, then you can verify it by:
(2046 $\cdot$ 8018 - 615)/8777 and seeing that the result is
an exact integer. [N.B. This is much faster than, for example,
repeatedly subtracting 8777 from 16404828 until getting
a number less than 8777; in this case that approach would
require 1869 subtractions!].
This same idea can also make quicker steps
of Euclid's Algorithm. 
\par
If you want to write a number, such as k=25920,
in base~2, then a fast way is as follows. Type 25920
into the calculator. At each step, we reduce the size of our
current number either by the step [divide-by-2]
(if our current number is even) or  
by the step [subtract-1-and-then-divide-by-2]
(if our current number is odd). This
allows us to write down the base~2 digits from right to left, where
we write down a~0 if we've done the first of the above,
and a~1 if we've done the second. For example,
with k=25920, we first perform [divide-by-2] and write
down~0 as our rightmost digit (and the calculator display
now reads 12960). After doing the [divide-by-2] 5 more
times, we have now written a total of 000000 as the
six rightmost digits, and the calculator reads: 405.
Now, perform [subtract-1-and-then-divide-by-2], and write
down a~1 on the left, so that your piece of paper
currently reads: 1000000, and your calculator
display reads: 202. Now perform [divide-by-2], so that
you piece of paper reads: 01000000 and your calculator
reads: 101. Continuing until your calculator reads 0
will make your final piece of paper read:
110010101000000; that is:
k = $\hbox{2}^{\hbox{\fiverm 6}}$ +
$\hbox{2}^{\hbox{\fiverm 8}}$ +
$\hbox{2}^{\hbox{\fiverm 10}}$ +
$\hbox{2}^{\hbox{\fiverm 13}}$ +
$\hbox{2}^{\hbox{\fiverm 14}}$ [take care to remember
that the last digit in 110010101000000 is the coefficient
of~$\hbox{2}^{\hbox{\fiverm 0}}$.]
\vfil \eject \end