Обчислення модульної експоненти для великих чисел широко використовується для знаходження дискретного логарифму, в теоретико-числових перетвореннях та в криптографічних алгоритмах. Для ефективного обчислення модульної експоненти проводяться дослідження нових методів, алгоритмів та засобів їх реалізації. Виділяють три напрями методів модульного піднесення до степеня: загальне модульне піднесення до степеня, та обчислення модульної експоненти з фіксованим показником або з фіксованою основою. Розроблено спеціальні функції для виконання піднесення до степені за модулем у математичних і криптографічних програмних бібліотеках. У роботі проведено порівняльний аналіз вільнодоступних функцій обчислення модульної експоненти з бібліотек Crypto++, OpenSSL, Pari/GP та MPIR та розроблених трьох функцій на основі алгоритму бінарного зсуву справа на ліво. Для роботи з великими числами у розроблених функціях використовується окремий тип числових даних з бібліотеки MPIR. Розроблені функції реалізують бінарний ітераційний алгоритм в одному основному потоці, у двох потоках та одному потоці з використанням передобчислення. За основу порівняння вибрано усереднений тривалість виконання обчислення модульної експоненти для псевдовипадкових даних розрядністю 1К і 2К біт, що відповідає розрядності біля 300 і 600 десяткових знаків. Результати часу виконання, що зведені у таблицю, показують, що найшвидше обчислюється модульна експонента функцією з бібліотеки OpenSSL в універсальних комп'ютерних системах. Реалізації математичними та криптографічними програмними бібліотеками функції обчислення модульної експоненти використовує більш оптимальний алгоритм множення за модулем, так зване множення Монтгомері. У розроблених трьох функціях використовуються операції множення за модулем для множників менших за значення модуля. Окремо проаналізовано функцію з використанням передобчислення залишків для фіксованої основи та модуля, що може ефективно використовуватись для обчислення дискретного логарифму.
[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.
[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].