Compact elliptic curve representations

Mathieu Ciet, Jean Jacques Quisquater, Francesco Sica

Research output: Contribution to journalArticle

Abstract

Let y 2 = x 3 + ax + b be an elliptic curve over F; p, p being a prime number greater than 3, and consider a; b ∈ [1, p]. In this paper, we study elliptic curve isomorphisms, with a view towards reduction in the size of elliptic curves coefficients. We first consider reducing the ratio a/b. We then apply these considerations to determine the number of elliptic curve isomorphism classes. Later we work on both coefficients. We introduce the number M.p/as the lower bound of all M ∈ ℕ such that each isomorphism class has a representative with max (a,b) < M. Using results from the theory of uniform distributions, we prove upper and lower bounds of the form c 1p1/2 < M(p) < c 2p 3/4 with explicit constants c 1, c 2 > 0.

Original languageEnglish
Pages (from-to)89-100
Number of pages12
JournalJournal of Mathematical Cryptology
Volume5
Issue number1
DOIs
Publication statusPublished - Jun 1 2011

    Fingerprint

Keywords

  • Cryptography
  • Elliptic curves
  • Exponential sums
  • Uniform distribution

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

Cite this