dc.contributor.author
Dieulefait, Luis
dc.contributor.author
Urroz, J.
dc.date.accessioned
2026-01-20T15:04:24Z
dc.date.available
2026-01-20T15:04:24Z
dc.date.issued
2025-11-27
dc.identifier.uri
http://hdl.handle.net/2072/489148
dc.description.abstract
In this paper, we give a polynomial time algorithm to compute Phi(N) for an RSA module N using as input the order modulo N of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least 1-(1 )/( N 1/2-epsilon) , where E is any small positive constant.
ca
dc.description.sponsorship
Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature.
ca
dc.format.extent
13 p.
ca
dc.relation.ispartof
Quantum Information Processing
ca
dc.rights
Attribution 4.0 International
*
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
*
dc.source
RECERCAT (Dipòsit de la Recerca de Catalunya)
dc.subject.other
Factorization of integers
ca
dc.subject.other
Shor's algorithm
ca
dc.subject.other
Euler's phi function
ca
dc.title
Computing phi(N) for an RSA module with a single quantum query
ca
dc.type
info:eu-repo/semantics/article
ca
dc.description.version
info:eu-repo/semantics/publishedVersion
ca
dc.identifier.doi
10.1007/s11128-025-05008-w
ca
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
