Efficient Big Integer Multiplication in Cryptography
Abstract
Most of the public key cryptography algorithms require efficient big integer multiplications. In this paper, we show how to develop efficient integer multiplication algorithms for cryptographic applications by combining different methods. We determine the complexities by taking into account the cost of single word multiplication, single word addition and double word addition on different platforms. This paper is an extended version of [11]. We add the complexity of the last term method that is used for computing complexity of multiplication of degree n - 1 polynomials from the product of degree n - 2 polynomials. The unbalanced refined Karatsuba 2-way multiplication algorithm is also included. These new contributions improved the complexity results introduced in [11]. Moreover, we present the best multiplication algorithm complexities for NIST primes on different implementation platforms.
Keywords
References
- Cenk, M., & Hasan, M. A. (2015). Some new results on binary polynomial multiplication. Journal of Cryptographic Engineering, 5(4), 289-303. 1345-1361.
- Karatsuba, A. (1963). Multiplication of multidigit numbers on automata. In Sov. Phys. Dokl. (Vol. 7, No. 7, pp. 595-596).
- Bernstein, D. (2009). Batch binary Edwards. In: Advances in Cryptology CRYPTO 2009, LNCS, (vol. 5677, pp. 317336 ).
- Zhou, G., & Michalik, H. (2010). Comments on” A New Archi- tecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Field”. IEEE Transactions on Computers, 59(7), 1007-1008.
- Toom, A. L. (1963). The complexity of a scheme of functional elements realizing the multiplication of integers. In Soviet Math- ematics Doklady (Vol. 3, No. 4, pp. 714-716).
- Cook, S. A., & Aanderaa, S. O. (1969). On the minimum computation time of functions. Transactions of the American Mathematical Society, 142, 291-314.
- Harvey, D., Van Der Hoeven, J., & Lecerf, G. (2016). Even faster integer multiplication. Journal of Complexity, 36, 1-30.
- Weimerskirch, A., & Paar, C. (2006). Generalizations of the Karatsuba Algorithm for Efficient Implementations. IACR Cryp- tology ePrint Archive, 2006, 224.
Details
Primary Language
English
Subjects
-
Journal Section
-
Publication Date
December 1, 2017
Submission Date
-
Acceptance Date
-
Published in Issue
Year 2017 Volume: 6 Number: 4
APA
İlter, M. B., & Cenk, M. (2017). Efficient Big Integer Multiplication in Cryptography. International Journal of Information Security Science, 6(4), 70-78. https://izlik.org/JA92NY33YG
AMA
1.İlter MB, Cenk M. Efficient Big Integer Multiplication in Cryptography. IJISS. 2017;6(4):70-78. https://izlik.org/JA92NY33YG
Chicago
İlter, Murat Burhan, and Murat Cenk. 2017. “Efficient Big Integer Multiplication in Cryptography”. International Journal of Information Security Science 6 (4): 70-78. https://izlik.org/JA92NY33YG.
EndNote
İlter MB, Cenk M (December 1, 2017) Efficient Big Integer Multiplication in Cryptography. International Journal of Information Security Science 6 4 70–78.
IEEE
[1]M. B. İlter and M. Cenk, “Efficient Big Integer Multiplication in Cryptography”, IJISS, vol. 6, no. 4, pp. 70–78, Dec. 2017, [Online]. Available: https://izlik.org/JA92NY33YG
ISNAD
İlter, Murat Burhan - Cenk, Murat. “Efficient Big Integer Multiplication in Cryptography”. International Journal of Information Security Science 6/4 (December 1, 2017): 70-78. https://izlik.org/JA92NY33YG.
JAMA
1.İlter MB, Cenk M. Efficient Big Integer Multiplication in Cryptography. IJISS. 2017;6:70–78.
MLA
İlter, Murat Burhan, and Murat Cenk. “Efficient Big Integer Multiplication in Cryptography”. International Journal of Information Security Science, vol. 6, no. 4, Dec. 2017, pp. 70-78, https://izlik.org/JA92NY33YG.
Vancouver
1.Murat Burhan İlter, Murat Cenk. Efficient Big Integer Multiplication in Cryptography. IJISS [Internet]. 2017 Dec. 1;6(4):70-8. Available from: https://izlik.org/JA92NY33YG