1
$\begingroup$

I'm stuck with the following problem:

In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the action of $\psi = \psi_{N_1'}\circ\psi_{N_2}$ on $E[N_2],$ where $\psi_{N_1'}$ and $\psi_{N_2}$ are isogenies of degree respectively $N_1'$ and $N_2$ and $\psi = \psi_{N_1'}\circ\psi_{N_2}$ an endomorphism on the elliptic curve $E$.

Well, I don't understand this statement. I've tried writing $[N_2] = \psi_{N_2}\circ \hat{\psi}_{N_2}$ and then fiddling with the expressions, but to no avail.

I have a feeling this problem is easy, but I'm stuck and would appreciate any help/ideas.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The key details here are

  1. $N_2$ is "smooth by assumption", so solving discrete logarithms in $E[N_2]$ is supposed to be easy (using Pohlig-Hellman; how easy this is depends on how smooth $N_2$ is).
  2. $\gcd(N_1,N_2) = 1$, so the kernel of $\psi_2$ is equal to the kernel of the restriction of $\psi$ to $E[N_2]$.

Now, if you evaluate $\psi$ on a basis of $E[N_2]$, then by solving discrete logarithms you can view the restriction of $\psi$ to $E[N_2]$ as a matrix over $\mathbb{Z}/N_2\mathbb{Z}$, and then computing the kernel (and hence the kernel of $\psi_2$) is a matter of linear algebra.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think that i understood the second part: let $\psi|_{E[N_2]} : E[N_2] \to E[N_2](?)$ and $\{P,Q\}$ one basis of $E[N_2].$ Then i can write $\psi(P) = a_{11}P+a_{12}Q$ and $\psi(Q)=a_{21}P + a_{22}Q$ with $a_{ij} \in \mathbb{Z}/N_2\mathbb{Z}$ and I calculate the kernel as usual in such cases. I also understand why $\ker \psi_{N_2}\subseteq \ker \psi|_{E[N_2]},$ but not why $\ker \psi|_{E[N_2]}\subseteq \ker \psi_{N_2}$ $\endgroup$
    – Manuel Bravi
    Commented Feb 8, 2023 at 14:44
  • 1
    $\begingroup$ Since $\gcd(N_1',N_2) = 1$, the isogeny $\psi_{N_1'}$ restricts to an isomorphism on $N_2$-torsion; so $\psi(R) = 0$ for some $R$ in $E[N_2]$ iff $\psi_{N_2}(R) = 0$. $\endgroup$
    – Ben Smith
    Commented Feb 9, 2023 at 9:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .