So, here is the basic idea.
Consider the Weil pairing $e_N(P, Q)$ on an elliptic curve $E/K$ where $P, Q \in E[N]$. We start off by finding function $f \in \bar{K}(E)$ such that
$$(f) = N(P) - N(O)$$
Now set some notation, let $p = 1/N$ and let $q = \tau/N$. Now in our case it is very convenient that the Weierstrass $\sigma$-function allows us to construct a function with this divisor (see e.g., Silverman AEC, VI Prop 3.4) and the construction found there gives
$$f(z) = \frac{\sigma(z - 1/N)^N}{\sigma(z)^{N-1} \sigma(z - 1)}$$
Now we need to recall some facts about $\sigma(z)$, namely
Lemmas For $\omega \in \Lambda$ we have
$$\frac{\sigma(z + \omega)}{\sigma(z)} = \pm e^{\eta(\omega)(z + \omega/2)}$$
where the sign is positive if and only if $\omega \in 2 \lambda$, and $\eta$ satisfies
$$\tau\eta(1) - \eta(\tau) = 2\pi i$$
These facts are in Silverman Exercise 6.4.
With all that set up we can check
$$ f(z) = \frac{-1}{e^{\eta(1)(z + 1/2)}} \left( \frac{\sigma(z - 1/N)}{\sigma(z)} \right)^N$$
So that in the Weil pairing we choose
$$g(z) = \frac{\xi}{e^{\eta(1)(Nz + 1/2)/N}}\left( \frac{\sigma(Nz - 1/N)}{\sigma(Nz)} \right)$$
where $\xi^N = -1$, so that $g^N = f \circ [N]$.
Then we need to compute
$$e_N(p, q) = \frac{g(q + z)}{g(z)}$$
(where $z$ is so that we're not doing anything illegal). This will give
$$e_N(p, q) = \frac{1}{e^{\eta(1)\tau/N}} \frac{\sigma(Nz - 1/N + \tau) / \sigma(Nz + \tau)}{\sigma(Nz - 1/N) / \sigma(Nz)} $$
Using the lemmas we get
$$e_N(p, q) = \frac{e^{\eta(\tau)/N}}{e^{\eta(1)\tau/N}} = e^{2\pi i /N}$$
Finally, you can actually work throught this mess with some arbitrary lattice $\mathbb{Z} \omega_1 + \mathbb{Z} \omega_2$ so the assumptions on $\Lambda$ are not nessicary.
Also, I am sure to have made a sign error and come out with the wrong way around in my skew-symmetry, so please edit the post if you find such an error.
You can define the same concept for any finite abelian group $G$ and any positive integer $n$.
Let $e$ be the exponent of $G$. For any $n \in \mathbf{N}$, let $n' = \mathrm{gcd}(n, e)$. Then $G/nG \cong G[n']$, where the latter is the $n'$ torsion of $G$, induced by the map
$$G \to G[n']\\
g \mapsto (e/n')*g$$
In the case $G = \mathbf{F}_p^\times$ and $n = 2$, we have $e = p-1$ and recover the Legendre symbol
$$x \mapsto \left ( \frac{x}{p} \right ) = x^{e/2} \in \{\pm 1\} = (\mathbf{F}_p^\times)[2].$$
Let $E/\mathbf{F}_p$ be an elliptic curve. Let $H = E(\mathbf{F}_p) \cong \mathbf{Z}_{n_1} \oplus \mathbf{Z}_{n_2}$ with $n_1 \mid n_2$ (if $H$ is cyclic, just take $n_1 = 1$) and $P \in H$. We assume $2 \mid n_2$, otherwise $H/2H$ is trivial.
Then the class of $P$ in $H/2H$ is determined entirely by
$$(n_2/2) * P \in H[2] = E(\mathbf{F}_p)[2].$$
This, of course, can be computed in polynomial time.
Best Answer
An elliptic curve $$E:\qquad y^2=x^3+Ax+B$$ has an invariant differential $$\omega=\frac{dx}{2y}=\frac{dy}{3x^2+A}$$ which is characterised up to scalar multiplication that it has no zeros or poles. Given an endomorphism $$f:E\to E$$ the pullback $f^*\omega$ is a multiple of $\omega$: $$f^*\omega=c_f\omega.$$ Now $f\mapsto c_f$ is a ring homomorphism; it preserves addition and takes composition to composition.
Now if $E$ and $f$ are defined over $\Bbb Q$ then $c_f\in\Bbb Q$. So $f\mapsto c_f$ is a homomorphism from $\text{End}_{\Bbb Q}(E)$ to $\Bbb Q$ which is impossible if $\text{End}_{\Bbb Q}(E)$ contains an element outside $\Bbb Z$.