A tree-based approach for computing Double-Base chains

Christophe Doche*, Laurent Habsieger

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

20 Citations (Scopus)

Abstract

We introduce a tree-based method to find short Double-Base chains. As compared to the classical greedy approach, this new method is not only simpler to implement and faster, experimentally it also returns shorter chains on average. The complexity analysis shows that the average length of a chain returned by this tree-based approach is This tends to suggest that the average length of DB-chains generated by the greedy approach is not O(logn/loglogn). We also discuss generalizations of this method, namely to compute Step Multi-Base Representation chains involving more than 2 bases and extended DB-chains having nontrivial coefficients.

Original languageEnglish
Title of host publicationInformation security and privacy
Subtitle of host publication13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings
EditorsYi Mu, Willy Susilo, Jennifer Seberry
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages433-446
Number of pages14
ISBN (Print)3540699716, 9783540699712
DOIs
Publication statusPublished - 2008
Event13th Australasian Conference on Information Security and Privacy, ACISP 2008 - Wollongong, NSW, Australia
Duration: 7 Jul 20089 Jul 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5107 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other13th Australasian Conference on Information Security and Privacy, ACISP 2008
CountryAustralia
CityWollongong, NSW
Period7/07/089/07/08

Fingerprint Dive into the research topics of 'A tree-based approach for computing Double-Base chains'. Together they form a unique fingerprint.

Cite this