International Association
for Cryptologic Research

In the implementation of isogeny-based cryptographic schemes, Vélu’s formulas are essential for constructing and evaluating odd degree isogenies. Bernstein et al. proposed an approach known as √élu, which computes an ?-isogeny at a cost of̃ (√?) finite field operations. This paper presents two key improvements to enhance the efficiency of the implementation of √élu from two aspects: optimizing the partition involved in √élu and speeding up the computations of the sums of products used in polynomial multiplications over finite field ?? with large prime characteristic ?. To optimize the partition, we adjust it to enhance the utilization of ?-coordinates and eliminate the computational redundancy, which can ultimately reduce the number of ??-multiplications. The speedup of the sums of products is to employ two techniques: lazy reduction (abbreviated as LZYR) and generalized interleaved Montgomery multiplication (abbreviated as INTL). These techniques aim to minimize the underlying operations such as ??-reductions and assembly memory instructions. We present an optimized C and ssembly code implementation of √élu for the CTIDH512 instantiation. In terms of ?-isogeny computations in CTIDH512, the performance of clock cycles applying new partition + INTL (resp. new partition + LZYR) offers an improvement up to 16.05% (resp. 10.96%) compared to the previous work.