A tree-based approach for computing Double-Base chains

Christophe Doche; Laurent Habsieger

doi:10.1007/978-3-540-70500-0_32

A tree-based approach for computing Double-Base chains

Christophe Doche^*, Laurent Habsieger

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

24 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 language	English
Title of host publication	Information security and privacy
Subtitle of host publication	13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings
Editors	Yi Mu, Willy Susilo, Jennifer Seberry
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	433-446
Number of pages	14
ISBN (Print)	3540699716, 9783540699712
DOIs	https://doi.org/10.1007/978-3-540-70500-0_32
Publication status	Published - 2008
Event	13th Australasian Conference on Information Security and Privacy, ACISP 2008 - Wollongong, NSW, Australia Duration: 7 Jul 2008 → 9 Jul 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5107 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	13th Australasian Conference on Information Security and Privacy, ACISP 2008
Country/Territory	Australia
City	Wollongong, NSW
Period	7/07/08 → 9/07/08

Access to Document

10.1007/978-3-540-70500-0_32

Cite this

Doche, C., & Habsieger, L. (2008). A tree-based approach for computing Double-Base chains. In Y. Mu, W. Susilo, & J. Seberry (Eds.), Information security and privacy: 13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings (pp. 433-446). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5107 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-70500-0_32

Doche, Christophe ; Habsieger, Laurent. / A tree-based approach for computing Double-Base chains. Information security and privacy: 13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings. editor / Yi Mu ; Willy Susilo ; Jennifer Seberry. Berlin : Springer, Springer Nature, 2008. pp. 433-446 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{204b4f87b8e14754a6084b9f13d7f4f2,

title = "A tree-based approach for computing Double-Base chains",

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.",

author = "Christophe Doche and Laurent Habsieger",

year = "2008",

doi = "10.1007/978-3-540-70500-0_32",

language = "English",

isbn = "3540699716",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "433--446",

editor = "Yi Mu and Willy Susilo and Jennifer Seberry",

booktitle = "Information security and privacy",

address = "United States",

note = "13th Australasian Conference on Information Security and Privacy, ACISP 2008 ; Conference date: 07-07-2008 Through 09-07-2008",

}

Doche, C & Habsieger, L 2008, A tree-based approach for computing Double-Base chains. in Y Mu, W Susilo & J Seberry (eds), Information security and privacy: 13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5107 LNCS, Springer, Springer Nature, Berlin, pp. 433-446, 13th Australasian Conference on Information Security and Privacy, ACISP 2008, Wollongong, NSW, Australia, 7/07/08. https://doi.org/10.1007/978-3-540-70500-0_32

A tree-based approach for computing Double-Base chains. / Doche, Christophe; Habsieger, Laurent.
Information security and privacy: 13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings. ed. / Yi Mu; Willy Susilo; Jennifer Seberry. Berlin: Springer, Springer Nature, 2008. p. 433-446 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5107 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - A tree-based approach for computing Double-Base chains

AU - Doche, Christophe

AU - Habsieger, Laurent

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70349878789&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70500-0_32

DO - 10.1007/978-3-540-70500-0_32

M3 - Conference proceeding contribution

AN - SCOPUS:70349878789

SN - 3540699716

SN - 9783540699712

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 433

EP - 446

BT - Information security and privacy

A2 - Mu, Yi

A2 - Susilo, Willy

A2 - Seberry, Jennifer

PB - Springer, Springer Nature

CY - Berlin

T2 - 13th Australasian Conference on Information Security and Privacy, ACISP 2008

Y2 - 7 July 2008 through 9 July 2008

ER -

Doche C, Habsieger L. A tree-based approach for computing Double-Base chains. In Mu Y, Susilo W, Seberry J, editors, Information security and privacy: 13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 2008, proceedings. Berlin: Springer, Springer Nature. 2008. p. 433-446. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-70500-0_32

A tree-based approach for computing Double-Base chains

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this