In your particular case the order of the point divides $p-1$, this means that the embedding degree of your curve is 1.
You should be able to apply the MOV attack to transfer your instance of ECDLP into an instance of DLP over $\mathbb{F}_{p}^*$. This would allow you to use the Index Calculus to solve your problem.
As the Index Calculus is subexponential, it would improve the required time for your attack compared to a generic discrete logarithm attack on the elliptic curve (as the Rho or the BSGS).
To perform the MOV attack you should first find a point $R$ of order $n$ which is not a multiple of $P$. This should be easy given your curve. Proceed in the following way:
- Randomly generate a point $R$ on the curve
- Find its order
- Most likely it will be of the form $a*n$, if not goto step 1
- $R = [a]R$ will have order $n$
Then perform the Weil pairing of $P$ and $Q$ as:
$$
\begin{eqnarray}
w_1 &=& e(P, R) \\
w_2 &=& e(Q, R) = e(kP, R) = e(P, R)^k
\end{eqnarray}
$$
If $w_1 = 1$ then goto step 1. Otherwise solve the DLP by finding the $k$ of $w_2 = w_1{^k}$ in $\mathbb{F}_{p}^*$ using Index Calculus.
The returned $k$ will be the $k$ you are looking for (the one of $Q=[k]P$)
This answer by Samuel Neves, which I've used to write this answer, links to Sage code to compute the pairing and has more details.
Edit: Thanks Maarten for finding the goto issue.
k
's, I guess the intended attack route for this one is that this may be a weak curve and you can attack it this way, as even 71 bits for standard DLP algorithms is infeasible for most people $\endgroup$ – SEJPM♦ May 14 '15 at 15:55