Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 1/2018

28.08.2017

A fast optimal parallel algorithm for a short addition chain

verfasst von: Hazem M. Bahig

Erschienen in: The Journal of Supercomputing | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Given a natural number e, an addition chain for e is a finite sequence of numbers having the following properties: (1) the first number is one, (2) every element is the sum of two earlier elements, and (3) the given number occurs at the end of the sequence. We introduce a fast optimal algorithm to generate a chain of short length for the number e of n-bits. The algorithm is based on the right–left binary strategy and barrel shifter circuit. The algorithm uses \(O((\frac{n}{\log {n}})^2)\) processors and runs in \(O((\log {n})^2)\) time under exclusive read exclusive write parallel random access machine.
Vorheriger Artikel Survey on clustering in heterogeneous and homogeneous wireless sensor networks
Nächster Artikel On energy consumption of switch-centric data center networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Akl S (1997) Parallel computation: models and methods. Prentice Hall, Upper Saddle River
2.
3.
4.
5.
Bos J, Coster M (1990) Matthijs. Addition chain heuristics. In: Proceedings on advances in cryptology, vol 435. LNCS, pp 400–407
6.
Chin YH, Tsai YH (1985) Algorithms for finding the shortest addition chain. In: Proceedings of national computer symposium, Kaoshiung, Taiwan, Dec 20–22, pp 1398–1414
7.
8.
9.
Karp R, Ramachandran V (1990) Parallel Algorithms for Shared Memory Machines. In: Van Leeuwwen J (ed) Handbook of Theoretical Computer Science. Algorithm and Complexity, vol A. Elsevier, pp 869–941
10.
Khaled F, Hazem B, Hatem B, Ragab A (2011) Binary addition chain on EREW PRAM. In: Lecture notes in computer science, vol 7017, pp 321–330
11.
Knuth D (1973) The art of computer programming: seminumerical algorithms, vol 2. Addison-Wesley, BostonMATH
12.
Kunihiro N, Yamamoto H (1998) Window and extended window methods for addition chain and addition-substraction chain, special section on cryptography and information security. IEICE Trans Fundam E81–A:72–81
13.
Kunihiro N, Yamamoto H (2000) New methods for generating short addition chains. IEICE Trans Fundam E83–A(1):60–67
14.
Lee Y, Kim H, Hong S, Yoon H (2006) Expansion of sliding window method for finding shorter addition/subtraction-chains. Int J Netw Secur 2(1):34–40
15.
Li Y, Ma Q (2010) Design and implementation of layer extended shortest addition chains database for fast modular exponentiation in RSA. In: 2010 International Conference on Web Information Systems and Mining, China, IEEE proceeding, pp 136–139
16.
Jrvinen K, Dimitrov V, AzarderakhshA R (2015) Generalization of addition chains and fast inversions in binary fields. IEEE Trans Comput 64(9):2421–2432MathSciNetCrossRef
17.
Nedjah N, Mourelle LM (2002) Minimal addition chains using genetic algorithms. In: Proceedings of the Fifteenth International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Lecture notes in computer science, vol 2358, pp 88–98
18.
Nedjah N, Mourelle LM (2006) Towards minimal addition chains using ant colony optimization. J Math Model Algorithms 5(4):525–543MathSciNetCrossRefMATH
19.
Nedjah N, Mourelle LM (2011) High-performance SoC-based implementation of modular exponentiation using evolutionary addition chains for efficient cryptography. Appl Soft Comput 11:4302–4311CrossRef
20.
Rooij P (1995) Efficient Exponentiation using precomputation and vector addition chains. In: Advances in cryptology–EUROCRYPT ’94 (Perugia). Lecture notes in computer science, vol 950, pp 389–399
21.
Schonhage A, Strassen V (1971) Schnelle multiplikation GroBer Zahlen. Computing 7:281–292CrossRefMATH
22.
23.
Wakerly John F (2006) Digital design: principles and practices package. Prentice Hall, Upper Saddle RiverMATH
Metadaten
Titel
A fast optimal parallel algorithm for a short addition chain
verfasst von
Hazem M. Bahig
Publikationsdatum
28.08.2017
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 1/2018
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-017-2129-0

Weitere Artikel der Ausgabe 1/2018

The Journal of Supercomputing 1/2018 Zur Ausgabe

OriginalPaper

A comprehensive evaluation of availability and operational cost for a virtualized server system using stochastic reward nets

OriginalPaper

DoS, impersonation and de-synchronization attacks against an ultra-lightweight RFID mutual authentication protocol for IoT

OriginalPaper

ECCN: an extended CCN architecture to improve data access in vehicular content-centric network

OriginalPaper

Interactive 3D simulation for fluid–structure interactions using dual coupled GPUs

OriginalPaper

A Scalable and Lightweight Grouping Proof Protocol for Internet of Things Applications

OriginalPaper

A churn-aware durable data storage scheme in hybrid P2P networks