nach oben

Cryptography and Communications

Erschienen in:

07.03.2017

Missing a trick: Karatsuba variations

verfasst von: Michael Scott

Erschienen in: Cryptography and Communications | Ausgabe 1/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

There are a variety of ways of applying the Karatsuba idea to multi-digit multiplication. These apply particularly well in the context where digits do not use the full word-length of the computer, so that partial products can be safely accumulated without fear of overflow. Here we re-visit the “arbitrary degree” version of Karatsuba and show that the cost of this little-known variant has been over-estimated in the past. We also attempt to definitively answer the question as to the cross-over point where Karatsuba performs better than the classic method.

Vorheriger Artikel Editorial: Special issue on recent trends in cryptography

Nächster Artikel Backtracking-assisted multiplication

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

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

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"

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

Nur mit Berechtigung zugänglich

¹ This reference was brought to our attention by an anonymous reviewer of [4]

Bernstein, D.J., Chuengsatiansup, C., Lange, T.: Curve41417: Karatsuba revisited. Cryptology ePrint Archive, Report 2014/526. http://eprint.iacr.org/2014/526(2014)

Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed high-security signatures. Cryptology ePrint Archive, Report 2011/368. http://eprint.iacr.org/2011/368 (2011)

Brent, R., Zimmermann, P.: Modern computer arithmetic. Cambridge University Press, Cambridge (2010)CrossRefMATH

Granger, R., Scott, M.: Faster ECC over \({F}_{2^{521}-1}\) Public-Key Cryptography – PKC 2015, volume 9020 of Lecture Notes in Computer Science, pp 539–553. Springer, Berlin Heidelberg (2015)

Granger, R., Moss, A.: Generalised Mersenne numbers revisited. Math. Comput. 82, 2389–2420 (2013). arXiv:1108.3054 MathSciNetCrossRefMATH

Torbjörn Granlund and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library, 6.1.0 edn., 2015. http://gmplib.org/

Hamburg, M.: Ed448-Goldilocks, a new elliptic curve. Cryptology ePrint Archive, Report 2015/625. http://eprint.iacr.org/2015/625 (2015)

Khachatrian, G., Kuregian, M., Ispiryan, K., Massey, J.: Faster multiplication of integers for public-key applications Selected Areas in Cryptography, volume 2259 of Lecture Notes in Computer Science, pp 245–254. Springer, Berlin Heidelberg (2001)

Montgomery, P.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)MathSciNetCrossRefMATH

10.

Montgomery, P.: Five, six and seven term Karatsuba-like formulae. IEEE Trans. Comput. 54(3), 362–369 (2005)CrossRefMATH

11.

Nogami, Y., Saito, A., Morikawa, Y.: Finite extension field with modulus of all-one polynomial and representation of its elements for fast arithmetic operations. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86-A(9), 2376–2387 (2003)

12.

Weimerskirch, A., Paar, C.: Generalization of the Karatsuba algorithm for efficient implementations. Cryptology ePrint Archive, Report 2006/224. http://eprint.iacr.org/2006/224 (2006)

13.

Zimmermann, P.: Personal communication, January 2015

Titel: Missing a trick: Karatsuba variations
verfasst von: Michael Scott
Publikationsdatum: 07.03.2017
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 1/2018
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-017-0217-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2018

Efficient robust secret sharing from expander graphs

Malleability of the blockchain’s entropy

On generating invertible circulant binary matrices with a prescribed number of ones

POEx: A beyond-birthday-bound-secure on-line cipher

On the optimality and practicability of mutual information analysis in some scenarios

Security of BLS and BGLS signatures in a multi-user setting