Fast point decompression for standard elliptic curves

Billy Bob Brumley, Kimmo U. Järvinen

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

5 Citations (Scopus)


Many standard elliptic curves (e.g. NIST, SECG, ANSI X9.62, WTLS, ...) over the finite field have p a prime of Mersenne-like form-this yields faster field arithmetic. Point compression cuts the storage requirement for points (public keys) in half and is hence desirable. Point decompression in turn involves a square root computation. Given the special Mersenne-like form of a prime, in this paper we examine the problem of efficiently computing square roots in the base field. Although the motivation comes from standard curves, our analysis is for fast square roots in any arbitrary Mersenne-like prime field satisfying . Using well-known methods from number theory, we present a general strategy for fast square root computation in these base fields. Significant speedup in the exponentiation is achieved compared to general methods for exponentiation. Both software and hardware implementation results are given, with a focus on standard elliptic curves.

Original languageEnglish
Title of host publicationPublic Key Infrastructure - 5th European PKI Workshop
Subtitle of host publicationTheory and Practice, EuroPKI 2008, Proceedings
Number of pages16
Publication statusPublished - 1 Jul 2008
Externally publishedYes
Publication typeA4 Article in conference proceedings
Event5th European Public Key Infrastructure Workshop: Theory and Practice, EuroPKI 2008 - Trondheim, Norway
Duration: 16 Jun 200817 Jun 2008

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th European Public Key Infrastructure Workshop: Theory and Practice, EuroPKI 2008


  • Addition chains
  • Elliptic curve cryptography
  • Exponentiation
  • Square roots modulo p

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Fast point decompression for standard elliptic curves'. Together they form a unique fingerprint.

Cite this