Hide
Problem A
Elliptic Curve Arithmetic
Implement arithmetic for the standard elliptic curve prime192v3. This is a curve of the form $y^2=x^3+ax+b$ over $Z_ p$ with a standard generator $G=(g_ x,g_ y)\in Z_ p^2$ of order $q$, where:
\begin{eqnarray} p& =& \mbox{0xfffffffffffffffffffffffffffffffeffffffffffffffff}\\ a& =& \mbox{0xfffffffffffffffffffffffffffffffefffffffffffffffc}\\ b& =& \mbox{0x22123dc2395a05caa7423daeccc94760a7d462256bd56916}\\ g_ x& =& \mbox{0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896}\\ g_ y& =& \mbox{0x38a90f22637337334b49dcb66a6dc8f9978aca7648a943b0}\\ q& =& \mbox{0xffffffffffffffffffffffff7a62d031c83f4294f640ec13} \end{eqnarray}are positive integers represented in hexadecimal. (Note that, e.g., $p$ would be a negative integer if viewed as an integer in two’s complement.)
The point at infinity does not appear in this problem, so it can be represented anyway you like.
Input
Each line of the input consists of a single positive exponent $e$ represented as a hexadecimal string.
Output
For each input line, output a line containing a space-separated pair of integers $x$ and $y$ in $Z_ p$ such that $(x,y)=eG$ represented in hexadecimal basis.
| Sample Input 1 | Sample Output 1 |
|---|---|
0x5caa7423daecc1da1783716588d3daecc1da17844444 0x5823acc1d781d3daec165837a74da8a17daecc17daec 0x038a90f22637337334b49dcb66a6dc8f9978aca7648a |
0x7d62fc2425f8433957ac86bb7f8da086136b1c6e5a2f3433 0xd38d6290d6e7d373ed7a8a9e9330500d0bfd9b204d76cbfe 0x4741e9fd56f7089f521ac5e5330a7ecccfbbca9f71f1e112 0x6883368a7ddf3c9dfb98c51cd8159e6e4c005c4ab5e26f62 0xb1dd4a86ac61c45799032babbf0c316543b47d10427e3226 0x95a2110b07ad66480dce3a6ac4279aa6c88ddfc9ea609a0a |
