{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:00:31Z","timestamp":1760148031945,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>In the field of cryptography, many algorithms rely on the computation of modular multiplicative inverses to ensure the security of their systems. In this study, we build upon our previous research by introducing a novel sequence, (zj)j\u22650, that can calculate the modular inverse of a given pair of integers (a,n), i.e., a\u22121;mod,n. The computational complexity of this approach is O(a), which is more efficient than the traditional Euler\u2019s phi function method, O(n,ln,n). Furthermore, we investigate the properties of the sequence (zj)j\u22650 and demonstrate that all solutions of the problem belong to a specific set, I, that only contains the minimum values of (zj)j\u22650. This results in a reduction of the computational complexity of our method, especially when a\u223cn and it also opens new opportunities for discovering closed-form solutions for the modular inverse.<\/jats:p>","DOI":"10.3390\/computation11040070","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T07:32:09Z","timestamp":1679902329000},"page":"70","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Some Properties of the Computation of the Modular Inverse with Applications in Cryptography"],"prefix":"10.3390","volume":"11","author":[{"given":"Michele","family":"Bufalo","sequence":"first","affiliation":[{"name":"Department of Methods and Models for Economics, Territory and Finance, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, Via del Castro Laurenziano 9, 00185 Rome, Italy"}]},{"given":"Daniele","family":"Bufalo","sequence":"additional","affiliation":[{"name":"Department of Informatics, Universit\u00e0 degli Studi di Bari Aldo Moro, Via Orabona 4, 70125 Bari, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2630-5403","authenticated-orcid":false,"given":"Giuseppe","family":"Orlando","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Universit\u00e0 degli Studi di Bari Aldo Moro, Via Orabona 4, 70125 Bari, Italy"},{"name":"Department of Economics, HSE University, Soyuza Pechatnikov Street 16, 190121 St. Petersburg, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,27]]},"reference":[{"key":"ref_1","unstructured":"Rivest, R.L., Shamir, A., and Adleman, L.M. (1983). Cryptographic Communications System and Method. (4,405,829), US Patent."},{"key":"ref_2","unstructured":"Crandall, R., and Pomerance, C.B. (2006). Prime Numbers: A Computational Perspective, Springer Science & Business Media."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_4","unstructured":"Verkhovsky, B. (2001, January 22\u201325). Overpass-Crossing Scheme for Digital Signature. Proceedings of the International Conference on System Research, Informatics and Cybernetics, Baden-Baden, Germany."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"901","DOI":"10.4236\/ijcns.2010.312123","article-title":"Enhanced Euclid Algorithm for Modular Multiplicative Inverse and Its Application in Cryptographic Protocols","volume":"3","author":"Verkhovsky","year":"2010","journal-title":"IJCNS"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","author":"ElGamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","unstructured":"Rabin, M.O. (1979). Digitalized Signatures and Public-Key Functions as Intractable as Factorization, Massachusetts Institute of Technology Cambridge Lab for Computer Science. Technical Report."},{"key":"ref_8","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H., and Silverman, J.H. (2008). An Introduction to Mathematical Cryptography, Springer."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Sosa-G\u00f3mez, G., Paez-Osuna, O., Rojas, O., and Madarro-Cap\u00f3, E.J. (2021). A New Family of Boolean Functions with Good Cryptographic Properties. Axioms, 10.","DOI":"10.3390\/axioms10020042"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bufalo, M., Bufalo, D., and Orlando, G. (2021). A Note on the Computation of the Modular Inverse for Cryptography. Axioms, 10.","DOI":"10.3390\/axioms10020116"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bufalo, D., Bufalo, M., Orlando, G., and Tetta, R. (J. Discret. Math. Sci. Cryptogr., 2023). A new algorithm to find prime numbers with less memory requirements, J. Discret. Math. Sci. Cryptogr., in press.","DOI":"10.47974\/JDMSC-1629"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Somani, U., Lakhani, K., and Mundra, M. (2010, January 28\u201330). Implementing digital signature with RSA encryption algorithm to enhance the Data Security of cloud in Cloud Computing. Proceedings of the 2010 First International Conference on Parallel, Distributed and Grid Computing (PDGC 2010), Solan, India.","DOI":"10.1109\/PDGC.2010.5679895"},{"key":"ref_13","first-page":"3949","article-title":"Enhanced RSA cryptosystem based on multiplicity of public and private keys","volume":"8","author":"Mezher","year":"2018","journal-title":"Int. J. Electr. Comput. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kumar, V., Kumar, R., and Pandey, S. (2017, January 30\u201331). An enhanced and secured RSA public key cryptosystem algorithm using Chinese remainder theorem. Proceedings of the International Conference on Next Generation Computing Technologies, Dehradun, India.","DOI":"10.1007\/978-981-10-8660-1_42"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"78","DOI":"10.4236\/jcc.2018.63006","article-title":"A modified and secured RSA public key cryptosystem based on \u201cn\u201d prime numbers","volume":"6","author":"Islam","year":"2018","journal-title":"J. Comput. Commun."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"e4845","DOI":"10.1002\/cpe.4845","article-title":"An efficient RSA cryptosystem by applying cuckoo search optimization algorithm","volume":"31","author":"Rajesh","year":"2019","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/09720529.2018.1564201","article-title":"Forty years of attacks on the RSA cryptosystem: A brief survey","volume":"22","author":"Mumtaz","year":"2019","journal-title":"J. Discret. Math. Sci. Cryptogr."},{"key":"ref_18","first-page":"125","article-title":"Dual-Basis Superserial Multipliers for Secure Applications and Lightweight Cryptographic Architectures","volume":"61","author":"Kermani","year":"2013","journal-title":"IEEE Trans. Circuits Syst. II Express Briefs"},{"key":"ref_19","unstructured":"Biham, E., and Shamir, A. (2006). Advances in Cryptology\u2014CRYPTO \u201997, Springer."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s001450010016","article-title":"On the Importance of Eliminating Errors in Cryptographic Computations","volume":"14","author":"Boneh","year":"2001","journal-title":"J. Cryptol."},{"key":"ref_21","unstructured":"Boneh, D., DeMillo, R.A., and Lipton, R.J. (2001). Advances in Cryptology\u2014EUROCRYPT \u201997, Springer."},{"key":"ref_22","unstructured":"Ali, S., Guo, X., Karri, R., and Mukhopadhyay, D. (2016). Secure System Design and Trustable Computing, Springer."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/LES.2015.2477273","article-title":"Strengthening SIMON Implementation Against Intelligent Fault Attacks","volume":"7","author":"Dofe","year":"2015","journal-title":"IEEE Embed. Syst. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3719","DOI":"10.1109\/TCSI.2021.3094889","article-title":"High-Speed FPGA Implementation of SIKE Based on an Ultra-Low-Latency Modular Multiplier","volume":"68","author":"Tian","year":"2021","journal-title":"IEEE Trans. Circuits Syst. I Regul. Pap."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"LaPierre, R. (2021). Introduction to Quantum Computing, Springer.","DOI":"10.1007\/978-3-030-69318-3"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mozaffari-Kermani, M., and Azarderakhsh, R. (2015, January 12\u201314). Reliable hash trees for post-quantum stateless cryptographic hash-based signatures. Proceedings of the 2015 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFTS), Amherst, MA, USA.","DOI":"10.1109\/DFT.2015.7315144"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Dubrova, E., Ngo, K., and G\u00e4rtner, J. (2023, March 20). Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste. Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2022\/1713.","DOI":"10.1145\/3591866.3593072"},{"key":"ref_28","unstructured":"Berzati, A., Viera, A.C., Chartouni, M., Madec, S., Vergnaud, D., and Vigilant, D. (2023, March 20). A Practical Template Attack on CRYSTALS-Dilithium. Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2023\/050."},{"key":"ref_29","unstructured":"Steed, H. (2023, January 20). Integer-Complexity-Bound-of-Post-Quantum-Cryptography. Available online: https:\/\/github.com\/steedhuang\/Integer-Complexity-Bound-of-Post-Quantum-Cryptography."},{"key":"ref_30","unstructured":"Zhang, Y. (2022). Discrete mean estimates and the Landau-Siegel zero. arXiv."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/4\/70\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:04:05Z","timestamp":1760123045000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/4\/70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,27]]},"references-count":30,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["computation11040070"],"URL":"https:\/\/doi.org\/10.3390\/computation11040070","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2023,3,27]]}}}