• I. Prots’ko Lviv National Polytechnic University, Lviv, Ukraine, Ukraine
  • O. Gryshchuk LtdС “SoftServe”, Lviv, Ukraine, Ukraine



modular exponentiation, big numbers, exponentiation algorithm, fixed-base exponentiation, residual set


Context. Modular exponentiation is an important operation in many applications that requires a large number of calculations 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 program that uses the precomputation of redused set of residuals for fixed-base.

Method. Modular exponentiation is implemented using of the development of the right-to-left binary exponentiation method for a fixed basis with precomputation of redused set of residuals. To efficient compute the modular exponentiation over big numbers, the property of a periodicity for the sequence of residuals of a fixed base with exponents equal to an integer power of two is used.

Results. Comparison of the runtimes of five variants of functions for computing the modular exponentiation is performed. In the algorithm with precomputation of redused set of residuals for fixed-base provide faster computation of modular exponentiation for values larger than 1K binary digits compared to the functions of modular exponentiation of the MPIR and Crypto++ libraries. 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.

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 the precomputation of redused set of residuals for fixed-base. The software implementation of modular exponentiation with increasing from 1K the number of binary digit of exponent shows an improvement of computation time with comparison with the functions of modular exponentiation of the MPIR and Crypto++ libraries.

Author Biographies

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

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

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

Software Developer


Studholme C. The Discrete Log Problem [Electronic resource]. Department of Computer Science, University of Toronto, 2002, 57 p. Access mode: http://www.cs.toronto. edu/~cvs/dlog/research_paper.pdf

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

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

Lara P., Borges F., Portugal R., Nedjah N. Parallel modular exponentiation using load balancing without precomputation, Journal of Computer and System Sciences, 2012, Vol. 78, No. 2, pp. 575–582.

Nedjah N., Mourelle Ld. M. Three hardware architectures for the binary modular exponentiation: Sequential, parallel, and systolic, Circuits and Systems I: Regular Papers, IEEE Transactions, 2006. Vol. 53, Issue 3, pp. 627–633. 10.1109/TCSI.2005.858767.

Vollala S., Ramasubramanian N., Tiwari U. EnergyEfficient Modular Exponential Techniques for Public-Key Cryptography. Springer Nature, Singapur, Pte Ltd. 2021, 255 p.

PARI/GP home. [Electronic resource]. Access mode:

MPIR: Multiple Precision Integers and Rationals. [Electronic resource]. Access mode:

Crypto++ Library 8.6 Electronic resource]. Access mode:

Knuth D. E. The art of computer programming. 3d ed. Reading (Mass), Addison-Wesley, cop. 1998, 712 p.

Bach E., Shallit J. Algorithmic Number Theory, Volume I, Efficient Algorithms. Cambridge, USA: MIT Press. 1996, 516 p.

Cohen H. A course in computational algebraic number theory. Berlin, Heidelberg, Springer. 1993, 536 p.

Menezes A. J., Oorschot van P. C., Vanstone S. A.. Handbook of Applied Cryptography, 5th printing, Boca Raton. CRC Press, 2001, 816 p.

Sorenson J. P. [Electronic resource] A sublinear-time parallel algorithm for integer modular exponentiation, 1999. pp. 1–8. Access mode:

Robert J.-M., Negre C., Plantard T. Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding, Journal of Cryptographic Engineering, Springer, 2019, Vol. 9, Issue 2, pp. 115–136.

Joye M. and Tunstall M. Exponent Recoding and Regular Exponentiation Algorithms, Conference on Cryptology in Africa (Africacrypt 2009): Second International Conference. Gammarth, Tunisia, 2009, proceedings. Published by Springer, 2009, pp. 334–349.

Rosen K. H. Elementary number theory and its applications 6th ed., China: Pearson/Addison Wesley, 2011, 721 p.

Prots’ko I. Kryvinska N., Gryshchuk O. The Runtime Analysis of Computation of Modular Exponentiation, Radio Electronics, Computer Science, Control, 2021, No. 3, pp. 42–47. DOI:




How to Cite

Prots’ko, I., & Gryshchuk, O. (2022). THE MODULAR EXPONENTIATION WITH PRECOMPUTATION OF REDUSED SET OF RESIDUES FOR FIXED-BASE . Radio Electronics, Computer Science, Control, (1), 58.



Mathematical and computer modelling