Bufalo, Michele and Bufalo, Daniele and Orlando, Giuseppe (2023) Some Properties of the Computation of the Modular Inverse with Applications in Cryptography. Computation, 11 (4). p. 70. ISSN 2079-3197
computation-11-00070.pdf - Published Version
Download (517kB)
Abstract
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≥0
, that can calculate the modular inverse of a given pair of integers (a,n)
, i.e., a−1;mod,n
. The computational complexity of this approach is O(a)
, which is more efficient than the traditional Euler’s phi function method, O(n,ln,n)
. Furthermore, we investigate the properties of the sequence (zj)j≥0
and demonstrate that all solutions of the problem belong to a specific set, I
, that only contains the minimum values of (zj)j≥0
. This results in a reduction of the computational complexity of our method, especially when a∼n
and it also opens new opportunities for discovering closed-form solutions for the modular inverse.
Item Type: | Article |
---|---|
Subjects: | Open Library Press > Computer Science |
Depositing User: | Unnamed user with email support@openlibrarypress.com |
Date Deposited: | 31 May 2023 05:53 |
Last Modified: | 31 May 2023 05:53 |
URI: | https://openlibrarypress.com/id/eprint/1469 |