The computation of the modular exponentiation for big numbers is widely used to find the discrete logarithm, in number-theoretic transforms and in cryptographic algorithms. To efficient compute the modular exponent, new methods, algorithms and means of their implementation are being developed. There are three directions of computational method of modular exponentiation: general modular exponentiation, and computation of the modular exponentiation with a fixed exponent or with a fixed base. Special functions have been developed to perform modular exponentiation in mathematical and cryptographic software libraries. The paper compares the freely available functions of computing the modular exponentiation from the Crypto ++, OpenSSL, Pari / GP and MPIR libraries and developed three functions based on the right-to-left binary shift algorithm. A separate type of numeric data from the MPIR library is used to work with big numbers in the developed functions. The developed functions implement a binary iterative algorithm in one main stream, in two streams and one stream using precomputation. The comparison is based on the average time of execution of the modular exponentiation for pseudo-random data with 1K and 2K bits, which corresponds to the size of about 300 and 600 decimal signs. The runtime results summarized in the table show that the modular exponentiation is computed the fastest by a function from the OpenSSL library, which is almost twice smaller than the function from the Crypto ++ library and three times smaller than the MPIR function in universal computer systems. The implementation of the function of computing the modular exponentiation by mathematical and cryptographic software libraries uses a more optimal modulus multiplication algorithm, the so-called Montgomery multiplication. The developed three functions use multiplication by modulo operations for factors smaller than the module value. The function using precomputation of the remainders for the fixed basis and the module is analyzed separately. After all, in the testing process, the time of precomputation and determination of the periodicity of residues for this function is not taken into account. Further parallelization of the computation of parts of a multi-bit exponent and the use of the Montgomery multiplication algorithm will allow efficient use of the developed function with precomputation for the calculation of the discrete logarithm.
[1] Studholme, C. (2002). The Discrete Log Problem. Retrieved from: http://www.cs.toronto.edu/~cvs/dlog/research_paper.pdf
[2] Satyanarayana, V. N., & Ramasubramanian, U. T. (2021). Energy-Efficient Modular Exponential Techniques for Public-Key Cryptography. Springer Nature Singapur Pte Ltd. 255 p.
https://doi.org/10.1007/978-3-030-74524-0
[3] Tandrup, M. B., Jensen, M. H., Andersen, R. N., & Hansen, T. F. (2004). Fast Exponentiation In practice. Retrieved from: https://cs.au.dk/~ivan/FastExpproject.pdf
[4] Jakubski, A., & Perliński, R. (2011). Review of General Exponentiation Algorithms. Scientific Research of the Institute of Mathematics and Computer Science, 2(10), 87–98. Retrieved from: http://amcm.pcz.pl/2011_2/art_10.pdf
[5] Rezai, A., & Keshavarzi, P. (2015). Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers. RAIRO – Theoretical Informatics and Applications, 49(3), 255–268.
https://doi.org/10.1051/ita/2015007
[6] Marouf, I., Asad, M. M., & Al-Haija, Q. A. (2017). Comparative Study of Efficient Modular Exponentiation Algorithms. COMPUSOFT, International journal of advanced computer technology, 6(8), 2381–2392.
[7] Vollala, S., Geetha, K., & Ramasubramanian, N. (2016). Efficient modular exponential algorithms compatible with hardware implementation of public-key cryptography. Security and Communication Networks, 9(16), 3105–3115.
https://doi.org/10.1002/sec.1511
[8] Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of applied cryptography. CRC Press, Boca Raton.
https://doi.org/10.1201/9780429466335
[9] Knuth, D. E. (1998). The art of computer programming. 3 d ed. Reading (Mass): Addison-Wesley, cop. 712 p.
[10] Bach, E., & Shallit, J. (1996). Algorithmic Number Theory. Volume I: Efficient Algorithms. Cambridge, USA: MIT Press. 516 p.
[11] Cohen, H. (1993). A course in computational algebraic number theory. Berlin, Heidelberg: Springer. 536 p.
https://doi.org/10.1007/978-3-662-02945-9
[12] Robert, J.-M., Negre, C., & Plantard, T. (2019). Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding. Journal of Cryptographic Engineering, Springer, 9(2), 115–136. https://doi.org/10.1007/s13389-018-0196-7
[13] Lara, P., Borges, F., Portugal, R., & Nedjah, N. (2012). Parallel modular exponentiation using load balancing without precomputation. Journal of Computer and System Sciences, 78(2), 575–582.
https://doi.org/10.1016/j.jcss.2011.07.002
[14] Nedjah, N., & Mourelle, Ld. M. (2006). Three hardware architectures for the binary modular exponentiation: Sequential, parallel, and systolic. Circuits and Systems I: Regular Papers, IEEE Transactions, 53(3), 627–633. https://doi.org/10.1109/TCSI.2005.858767
[15] Emmart, N., Zheng, F., & Weems, C. (2018). Faster Modular Exponentiation using Double Precision Floating Point Arithmetic on the GPU. 25th IEEE Symposium on Computer Arithmetic, 126–133.
https://doi.org/10.1109/ARITH.2018.8464792
[16] Gopal, V., Guilford, J., Ozturk, E., Feghali, W, Wolrich, G., & Dixon, M. (2009). Fast and Constant-Time Implementation of Modular Exponentiation. 28th International Symposium on Reliable Distributed Systems. Niagara Falls, New York, USA. Retrieved from: https://cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf
[17] Comparison of cryptography libraries. Retrieved from: https://en.wikipedia.org/wiki/Comparison_of_cryptography_libraries
[18] Negre, C., & Plantard, T. (2017). Efficient Regular Modular Exponentiation Using Multiplicative Half-Size Splitting. Journal of Cryptographic Engineering, Springer, 7(3), 245–253.
https://doi.org/10.1007/s13389-016-0134-5
[19] Gueron, S. (2012). Efficient software implementations of modular exponentiation. Journal of Cryptographic Engineering, 2, 31–43.
https://doi.org/10.1007/s13389-012-0031-5
[20] Protsko, 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
[21] Protsko, I., & Gryshchuk, O. (2022). The Modular Exponentiation with precomputation of redused set of resedues for fixed-base. Radio Electronics, Computer Science, Control, 1. (accepted).
[22] PARI/GP home. Retrieved from: http://pari.math.u-bordeaux.fr/
[23] MPIR: Multiple Precision Integers and Rationals. Retrieved from: http://mpir.org/
[24] Crypto++ Library 8.6. Retrieved from: https://www.cryptopp.com
[25] OpenSSL. Cryptography and SSL/TLS Toolkit. Retrieved from: http://www.openssl.org/
[26] Montgomery, P. (1985). Modular Multiplication without Trial Division. Mathematics of Computation, 44(170), 519–521.
https://doi.org/10.1090/S0025-5718-1985-0777282-X
[27] Hars, L. (2004). Long Modular Multiplication for Cryptographic Applications. Retrieved from: https://eprint.iacr.org/2004/198.pdf
[28] Protsko, I. (2020). Binarno-bitovi alhorytmy: prohramuvannya i zastosuvannya. Navchalʹnyy posibnyk. Lviv: "Triada plyus". 120 p. [In Ukrainian].