You are looking at a specific version 20200428:121439 of this paper. See the latest version.

Paper 2020/485

Edwards curve points counting method and supersingular Edwards and Montgomery curves

Ruslan V. Skuratovskii

Abstract

We consider algebraic affine and projective curves of Edwards [3, 9] over the finite field ${{\text{F}}_{{{p}^{n}}}}$. It is known that many modern cryptosystems [11] can be naturally transformed into elliptic curves [5]. We research Edwards algebraic curves over a finite field, which are one of the most promising supports of sets of points which are used for fast group operations \cite{Bir}. We construct a new method for counting the order of an Edwards curve over a finite field. It should be noted that this method can be applied to the order of elliptic curves due to the birational equivalence between elliptic curves and Edwards curves. We not only find a specific set of coefficients with corresponding field characteristics for which these curves are supersingular, but we additionally find a general formula by which one can determine whether a curve ${{E}_{d}}[{{\mathbb{F}}_{p}}]$ is supersingular over this field or not. The method we have proposed has much less complexity $O\left( p\log _{2}^{2}p \right)$ at not large values $p$ in comparison with the best Schoof basic algorithm with complexity$O(log_{2}^{8}{{p}^{n}})$, as well as a variant of the Schoof algorithm that uses fast arithmetic, which has complexity $O(log_{2}^{4}{{p}^{n}})$, but works only for Elkis or Atkin primes. The embedding degree of the supersingular curve of Edwards over ${{\mathbb{F}}_{{{p}^{n}}}}$ in a finite field is investigated and the field characteristic, where this degree is minimal, is found. A birational isomorphism between the Montgomery curve and the Edwards curve is also constructed. A one-to-one correspondence between the Edwards supersingular curves and Montgomery supersingular curves is established. The criterion of supersingularity for Edwards curves is found over ${{\mathbb{F}}_{{{p}^{n}}}}$. \\

Note: Elliptic curve order counting algorithm.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
finite fieldelliptic curveEdwards curvegroup of points of an elliptic curve.
Contact author(s)
ruslcomp @ mail ru
History
2020-04-28: received
Short URL
https://ia.cr/2020/485
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.