Faster computation of isogenies of large prime degree

Authors

Abstract: Let

m a t h c a l E / m a t h b b F_{q}

be an elliptic curve, and

P

a point in

m a t h c a l E (m a t h b b F_{q})

of prime order

e l l

. V'elu's formulae let us compute a quotient curve

m a t h c a l E^{'} = m a t h c a l E / l a n g l e P a n g l e

and rational maps defining a quotient isogeny

p h i : m a t h c a l E o m a t h c a l E^{'}

in

i l d e O (e l l)

m a t h b b F_{q}

-operations, where the

i l d e O

is uniform in

q

.This article shows how to compute

m a t h c a l E^{'}

, and

p h i (Q)

for

Q

in

m a t h c a l E (m a t h b b F_{q})

, using only

i l d e O (s q r t e l l)

m a t h b b F_{q}

-operations, where the

i l d e O

is again uniform in

q

.As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.

Recommendations

Cited in

(91)

This page was built for publication: Faster computation of isogenies of large prime degree