Tampere University of Technology

TUTCRIS Research Portal

On modular decomposition of integers

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


Original languageEnglish
Title of host publicationProgress in Cryptology - AFRICACRYPT 2009 - Second International Conference on Cryptology in Africa, Proceedings
Number of pages17
Publication statusPublished - 9 Nov 2009
Externally publishedYes
Publication typeA4 Article in a conference publication
Event2nd International Conference on Cryptology in Africa, AFRICACRYPT 2009 - Gammarth, Tunisia
Duration: 21 Jun 200925 Jun 2009

Publication series

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


Conference2nd International Conference on Cryptology in Africa, AFRICACRYPT 2009


At Crypto 2001, Gallant et al. showed how to exploit fast endomorphisms on some specific classes of elliptic curves to obtain fast scalar multiplication. The GLV method works by decomposing scalars into two small portions using multiplications, divisions, and rounding operations in the rationals. We present a new simple method based on the extended Euclidean algorithm that uses notably different operations than that of traditional decomposition. We obtain strict bounds on each component. Additionally, we examine the use of random decompositions, useful for key generation or cryptosystems requiring ephemeral keys. Specifically, we provide a complete description of the probability distribution of random decompositions and give bounds for each component in such a way that ensures a concrete level of entropy. This is the first analysis on distribution of random decompositions in GLV allowing the derivation of the entropy and thus an answer to the question first posed by Gallant in 1999.


  • Elliptic curve cryptography, GLV method, Integer decompositions

Publication forum classification