THE RUNTIME ANALYSIS OF COMPUTATION OF MODULAR EXPONENTIATION

Authors

  • I. Prots’ko Lviv National Polytechnic University, Lviv, Ukraine., Ukraine
  • N. Kryvinska Comenius University in Bratislava, Slovakia
  • O. Gryshchuk LtdС “SoftServe”, Lviv, Ukraine., Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2021-3-4

Keywords:

modular exponentiation, parallel computation, multithreading, big numbers.

Abstract

Context. Providing the problem of fast calculation of the modular exponentiation requires the development of effective algorithmic methods using the latest information technologies. Fast computations of the modular exponentiation are extremely necessary for efficient computations in theoretical-numerical transforms, for provide high crypto capability of information data and in many other applications.

Objective – the runtime analysis of software functions for computation of modular exponentiation of the developed programs based on parallel organization of computation with using multithreading.

Method. Modular exponentiation is implemented using a 2k-ary sliding window algorithm, where k is chosen according to the size of the exponent. Parallelization of computation consists in using the calculation of the remainders of numbers raised to the power of 2i modulo, and their further parallel multiplications modulo.

Results. Comparison of the runtimes of three variants of functions for computing the modular exponentiation is performed. In the algorithm of parallel organization of computation with using multithreading provide faster computation of modular exponentiation for exponent values larger than 1K binary digits compared to the function of modular exponentiation of the MPIR library. The MPIR library with an integer data type with the number of binary digits from 256 to 2048 bits is used to develop an algorithm for computing the modular exponentiation with using multithreading.

Conclusions. In the work has been considered and analysed the developed software implementation of the computation of modular exponentiation on universal computer systems. One of the ways to implement the speedup of computing modular exponentiation is developing algorithms that can use multithreading technology on multi-cores microprocessors. The multithreading software implementation of modular exponentiation with increasing from 1024 the number of binary digit of exponent shows an improvement of computation time with comparison with the function of modular exponentiation of the MPIR library.

Author Biographies

I. Prots’ko, Lviv National Polytechnic University, Lviv, Ukraine.

Dr. Sc., Associate Professor, Department of Automated Control Systems.

N. Kryvinska, Comenius University in Bratislava

Dr. Sc., Professor, Department of Information System.

O. Gryshchuk, LtdС “SoftServe”, Lviv, Ukraine.

Software Developer.

References

Marouf I. Comparative Study of Efficient Modular Exponentiation Algorithms. / I. Marouf, M. M. Asad, Q. A. Al-Haija // COMPUSOFT, An international journal of advanced computer technology. – August-2017. – Vol. 6, Issue 8. – P. 2381–2392.

Cormen T. H. Introduction to Algorithms / [T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein]. – Cambridge, USA : MIT Press, 3rd edition, 2009. –1312 p.

Efficient modular exponentiation algorithms [Electronic resource]. – https://eli.thegreenplace.net/2009/03/28/ efficientmodular-exponentiation-algorithms

Prots’ko I. O. Computation factorization of number at chip multithreading mode / I. O. Prots’ko, O. V. Gryschuk // Radio Electronics, Computer Science, Control. – 2019. –№ 3. – P. 117–122. DOI: 10.15588/1607-3274-2019-3-13

Jakubski A. Review of General Exponentiation Algorithms / A. Jakubski, R. Perliński // Scientific Research of the Institute of Mathematics and Computer Science. –2011. – Vol. 2, № 10. – P. 87–98

Parallel modular exponentiation using load balancing without precomputation / [P. Lara, F. Borges, R. Portugal, N. Nedjah] // Journal of Computer and System Sciences. – 2012. – Vol. 78, № 2. – P. 575–582. https://doi.org/10.1016/j.jcss.2011.07.002

MPIR: Multiple Precision Integers and Rationals. [Electronic resource]. – Access mode: http://mpir.org/

Koç C.-K. Analysis of sliding window techniques for exponentiation / C.-K. Koç // Computers & Mathematics with Applications. – 1995. – № 30. – P. 17–24.

Childs L. N. A Concrete Introduction to Higher Algebra. Undergraduate texts in Mathematics. / L. N. Childs. – New York : Springer, Science+Business Media LLC, 3rd edition, 2009. DOI: 10.1007/978-0-387-74725-5

PARI/GP home. [Electronic resource]. – Access mode: http://pari.math.u-bordeaux.fr/

Sun D.-Z. How to compute modular exponentiation with large operators based on the right-to-left binary algorithm / Da-Zhi Sun, Zhen-Fu Cao, Yu Sun // Applied Mathematics and Computation. – 1 May 2006. – Vol. 176, Iss. 1, – P. 280–292 DOI: 10.1016/j.amc.2005.09.062

Montgomery P. Modular Multiplication without Trial Division / P. Montgomery // Mathematics of Computation. –1985. – Vol. 44, №170. – P. 519–521.

Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers / A. Rezai, P. Keshavarzi // RAIRO – Theoretical Informatics and Applications. – July-September 2015. – Vol. 49, Num. 3. – P. 255 – 268. DOI: 10.1051/ita/2015007

Downloads

Published

2021-10-06

How to Cite

Prots’ko, I., Kryvinska, N., & Gryshchuk, O. (2021). THE RUNTIME ANALYSIS OF COMPUTATION OF MODULAR EXPONENTIATION . Radio Electronics, Computer Science, Control, (3), 42–47. https://doi.org/10.15588/1607-3274-2021-3-4

Issue

No. 3 (2021): Radio Electronics, Computer Science, Control

Section

Mathematical and computer modelling

License

Copyright (c) 2021 І. Процько, Н. Кривінська, О. Грищук

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.