Using Velu's formulas in MAGMA

Question

Most isogeny-based cryptographic schemes rely on constructing an isogeny having a given kernel. That is, given an elliptic curve $E$ and a subgroup $G$ of points of $E$, there is interest in constructing an isogeny $\phi : E \rightarrow E_1$ into some elliptic curve $E_1$ such that the kernel of $\phi$ is $G$. The isogeny $\phi$ and curve $E_1$ can both be constructed through the use of Velu's formulas.

I'd like to perform this construction in MAGMA. MAGMA seems to natively support this somewhat, with a few functions defined here:

http://magma.maths.usyd.edu.au/magma/handbook/text/1443#16366

These functions seem to use the language of (subgroup) schemes, which I am unfamiliar with. From what I can tell it defines $\phi$ by specifying its kernel polynomial. I tried the following code below, but it doesn't give the result that I expect. In my case, I'd like the kernel of $\phi$ to be the subgroup generated by a single point $P$.

F := GF(83);
E := EllipticCurve([0, F ! 1]);
P := E ! [22,78];
R<x> := PolynomialRing(F);
f := x - P[1];
G := SubgroupScheme(E,f);
Order(P);
Points(G);

IsogenyFromKernel(G);

The output is:

21
{@ (22 : 5 : 1), (22 : 78 : 1), (0 : 1 : 0) @}

IsogenyFromKernel(G: Subgroup scheme of C defined by x + 61)
IsogenyFromKernel(C: C,f: x + 61)
In file "/magma/package/Geometry/CrvEll/subgroup_schemes.m", line 9, column 29:
>>     return IsogenyFromKernel(C, f, 0 : Check:=Check);
                               ^
Runtime error in 'IsogenyFromKernel': Does not appear to be a kernel in Isogeny

First, $P$ has order $21$ while the "subgroup" consists of three points: $P$, $-P$, and $Id(E)$. Does the polynomial have to contain the $x$ coordinates of every point in the subgroup? Is there a simpler way to do this?

Answer 1

I am the inventor of Supersingular Isogeny Diffie-Hellman. Magma for some ridiculous reason doesn't have this particular common construction built in. You can re-create it manually using

IsogenyFromKernel(E, &*{(x-(n*P)[1]) : n in [1..Order(P)-1]});

Essentially this command reconstructs the kernel polynomial (&* is the magma command corresponding to \prod in LaTeX).