Consider the elliptic curve $E$:$Y^2=x^3+x+18$ over $F_p,$ with $p=31.($While the numbers are small,

you still need to use methods that also work well for larger numbers, unless otherwise instructed. When

computing multiples, use the double$-$and$-$add algorithm or its variant based on ternary expansions.$)$

$($a$)$ Verify that there is a point $P$ in $E(F_p)$ with $x-$coordinate $10.$ Suppose the $Y-$coordinate is encoded

by just one extra bit $0,$ as we explained in class. Determine the exact $Y-$coordinate.

$($b$)$ Verify that the point $P$ in $($a$)$ has order $15$ in $E(F_p).($Do not compute all multiples of $P.)$ Based on

this verification, determine #$E(F_p)$ without performing any further group operations in $E(F_p).$ Is

it true that each element of $E(F_p)$ is of the form $mP$ for some minZ $?(10$ points$)$

$($c$)$ Alice and Bob would like to use the elliptic Diffie$-$Hellman key exchange $($ECDH$),$ based on the

above $p$ and $(E,P).$ They agree to use only the $x-$coordinates in the communications and the

shared secret key. Alice chooses her secret $n_A=7.$ Help her compute $x(Q_A).$

$($d$)$ Alice receives the $x-$coordinate $x(Q_B)=0$ from Bob. Without computing Bob's secret $n_B,$ help

Alice compute the shared secret key. $(10$ points$)($Hint: You need to first find either $Q_B$ or $-Q_B.)$

$($e$)$ Find Bob's secret $+-n_B(mod15)$ by solving the ECDLP $Q_B=n_{B}P$ with the Pohlig$-$Hellman

algorithm. $($When solving the ECDLP for points of small prime orders $3$ and $5,$ you may perform

exhaustive searches on the small sets of multiples of the points, if needed.$)$