Radical Isogenies Sample Clauses

Radical Isogenies. → ∈ ≥ ⟨ ⟩ Let E0 be a supersingular Xxxxxxxxxx curve over Fp and P0 a point of order N with N 4. Additionally, let E1 = E0/ P0 , and P1 a point of order N on E1 such that ϕˆ(P1) = P0 where ϕˆ is the dual of the N -isogeny ϕ : E0 E1. The pairs (E0, P0) and (E1, P1) uniquely determine Xxxx normal parameters (b0, c0) and (b1, c1) with bi, ci Fp. Castryck, Decru, and Xxxxxxxxxxx proved the existence of a function ϕN that maps (b0, c0) to (b1, c1) in such a way that it can be applied iteratively. This computes a chain of N -isogenies without the need to sample points of order N per iteration. As a consequence, by mapping a given supersingular Xxxxxxxxxx curve E/Fp and some point P of order N to its Xxxx normal form, we can evaluate E → [li] E without any points (except for sampling P ). Thus, it allows us to compute E → [li]k E without having to sample k points of order N . E V´elu [li] E ... [li]k E To Xxxx normal form To Xxxxxxxxxx N E(b0, c0) ϕ E(b1, c1) ... E(bk, ck) Notice that the top row and the bottom row of the diagram are isomorphic. The map ϕN is an elementary function in terms of b, c and α = N√ρ for a ∈ specific element ρ Fp(b, c): hence the name ‘radical’ isogeny. Over Fp, an N - − →' ∈ { } · − th root is unique whenever N and p 1 are co-prime (as the map x xN is then a bijection). Notice that this in particular holds for all odd primes li of a CSIDH prime p = h li 1 for a suitable cofactor h. Xxxxxxxx, Decru, and Xxxxxxxxxxx provided the explicit formulas of ϕN for N 2, 3, 4, 5, 7, 9, 11, 13 . For larger degrees the formulas could not be derived yet. They also suggest the use of radical isogenies of degree 4 and 9 instead of 2 and 3, respectively. Later work by Xxxxx and Xxxxxx [21] provides similar radical isogenies on Xxxxxxxxxx curves instead of Xxxx normal curves. Although their results are of theoretical interest, they only provide such radical isogenies for degree 3 and