After noticing this challenge was about elliptic curves, I could not resist having a try at it. The “description” consisted of the following data:

`p = 16857450949524777441941817393974784044780411511252189319 A = 16857450949524777441941817393974784044780411507861094535 B = 77986137112576 E: y^2 = x^3 + Ax + B over GF(p) P = (5732560139258194764535999929325388041568732716579308775, 14532336890195013837874850588152996214121327870156054248) Q = (2609506039090139098835068603396546214836589143940493046, 8637771092812212464887027788957801177574860926032421582) Q = secret * P flag = secret`

Hence the task is simply to compute the (discrete) logarithm of `Q`

with base
`P`

on an elliptic curve `E`

given by a Weierstraß equation
\[ E\colon\quad y^2=x^3+Ax+B \text. \]

This problem is generally infeasible in reasonable time for curves over prime
fields as large as $p$, hence we suspect the curve is particularly badly
chosen. `sage`

confirms this assumption:

`sage: p = 16857450949524777441941817393974784044780411511252189319 sage: A = 16857450949524777441941817393974784044780411507861094535 sage: B = 77986137112576 sage: E = EllipticCurve(GF(p), [0, 0, 0, A, B]) sage: E Elliptic Curve defined by y^2 = x^3 + 16857450949524777441941817393974784044780411507861094535*x + 77986137112576 over Finite Field of size 16857450949524777441941817393974784044780411511252189319 sage: E.order() 16857450949524777441941817393974784044780411511252189319 sage: E.order() == p True`

The order of $E$ is exactly the order of the base field $p$, hence the
additive transfer attack, also
known as “Smart-ASS attack” or “anomalous curve attack”, applies. We follow the
paper *The discrete logarithm problem on elliptic curves
of trace one* by Nigel Smart.

In short, it says that **$\log_PQ$ is the $p^0$-coefficient of the quotient $\psi_p([p]Q_p)/\psi_p([p]P_p)$ of the $p$-adic elliptic logarithms of the $p$-multiples of $p$-adic lifts $Q_p,P_p$ of the points $Q$ and $P$.** Phew, that’s quite a mouthful. Let’s have a look at the individual steps:

- We can easily interpret $E$ as an elliptic curve $E_p$ over the $p$-adic
numbers $\mathbb Q_p$ since this is a complete discrete valuation ring with
residue field $\mathbb F_p$.
To lift a point on $E$ to $E_p$, we need to lift one coordinate and compute
the other. Fortunately
`sage`

has an implementation of square roots for $p$-adics, hence we may simply lift $x$ to an element of $\mathbb Q_p$ (by taking any representant of $x$ in $\mathbb Z$ and interpreting that as an element of $\mathbb Q_p$) and compute $y := \sqrt{x^3+Ax+B}$. Of course there are, in general, two square roots, only one of which has $p^0$-coefficient equal to the $y$-coordinate of $P$: We need to pick that one in order to get the sign of the logarithm we eventually want to compute correct. - Once we have points $P_p$ and $Q_p$ on $E_p$ which reduce to $P$ and $Q$ on $E$, that is, modulo $p$, we can just compute $[p]P_p$ and $[p]Q_p$ on $E_p$ using the usual point addition formulas.
- The rest is unexpectedly easy (in practice):
`sage`

has an implementation of the formal group including its formal logarithm. That logarithm is a power series with coefficients in $\mathbb Q_p$ with the very nice property that it yields a group homomorphism from a subgroup $E_1(\mathbb Q_p)$ of $E_p$ (in which $[p]P_p$ and $[p]Q_p$ are included by construction) to the*additive*group $(\mathbb Q_p,+)$: Letting $f$ denote said power series, this homomorphism is given by \[ \psi_p\colon\; E_1(\mathbb Q_p) \to \mathbb Q_p,\;(x,y)\mapsto f(-x/y) \text. \](Strictly speaking, we should now be checking if $\psi_p$ is injective as this would guarantee that our final logarithm is correct, but in practice it works just fine.)Therefore we may transfer the problem of computing $\log_{P_p}Q_p$ to $(\mathbb Q_p,+)$, in which “logarithms” are just division. Of course, there may be many different lifts of $P$ and $Q$ to $E_p$ which yield different logarithms, but all of these logarithms have the same $p^0$-coefficient since the lifts come from the same points on $E$.

Finally, here’s an implementation producing the solution:

```
#!/usr/bin/env sage
p = 16857450949524777441941817393974784044780411511252189319
A = 16857450949524777441941817393974784044780411507861094535
B = 77986137112576
xP = 5732560139258194764535999929325388041568732716579308775
yP = 14532336890195013837874850588152996214121327870156054248
xQ = 2609506039090139098835068603396546214836589143940493046
yQ = 8637771092812212464887027788957801177574860926032421582
E = EllipticCurve(GF(p), [0, 0, 0, A, B])
assert E.order() == p
Qp = Qp(p, 2)
Ep = EllipticCurve(Qp, [0, 0, 0, A, B])
yPp = sqrt(Qp(xP) ** 3 + Qp(A) * Qp(xP) + Qp(B))
Pp = Ep(Qp(xP), (-yPp, yPp)[yPp[0] == yP])
yQp = sqrt(Qp(xQ) ** 3 + Qp(A) * Qp(xQ) + Qp(B))
Qp = Ep(Qp(xQ), (-yQp, yQp)[yQp[0] == yQ])
print('Pp = {}'.format(Pp))
print('Qp = {}'.format(Qp))
print('-' * 40)
lQ = Ep.formal_group().log()(- (p * Qp)[0] // (p * Qp)[1]) / p
print('log(Q) = {}'.format(lQ))
lP = Ep.formal_group().log()(- (p * Pp)[0] // (p * Pp)[1]) / p
print('log(P) = {}'.format(lP))
print('-' * 40)
e = lQ / lP
print('e = {}'.format(e))
assert e[0] * E(xP, yP) == E(xQ, yQ)
print('\n--> FLAG: {:d}\n'.format(e[0]))
```