THE MODULAR EXPONENTIATION WITH PRECOMPUTATION OF REDUSED SET OF RESIDUES FOR FIXED-BASE
DOI:
https://doi.org/10.15588/1607-3274-2022-1-7Keywords:
modular exponentiation, big numbers, exponentiation algorithm, fixed-base exponentiation, residual setAbstract
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.
References
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. https://doi.org/10.1016/j.jcss.2011.07.002
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. https://doi.org/ 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. https://doi.org/10.1007/978-3-030-74524-0
PARI/GP home. [Electronic resource]. Access mode: http://pari.math.u-bordeaux.fr/
MPIR: Multiple Precision Integers and Rationals. [Electronic resource]. Access mode: http://mpir.org/
Crypto++ Library 8.6 Electronic resource]. Access mode: https://www.cryptopp.com
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. https://doi.org/10.1007/978-3-662-02945-9
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: https://www.researchgate.net/publication/2274099_A
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. https://doi.org/10.1007/s13389-018-0196-7.
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: https://doi.org/10.15588/1607-3274-2021-3-4
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 I. Prots’ko, O. Gryshchuk
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.
