Dieulefait, Luis; Jiménez Urroz, Jorge Small primitive roots and malleability of RSA moduli. (English) Zbl 1245.11007 J. Comb. Number Theory 2, No. 2, 171-179 (2010). Summary: P. Paillier and J. Villar [Lect. Notes Comput. Sci. 4284, 252–266 (2006; Zbl 1172.94593)] made a conjecture about the malleability of an RSA modulus. In this paper we present an explicit algorithm refuting the conjecture. Concretely we can factorize an RSA modulus \(n\) using very little information on the factorization of a concrete \(n'\) coprime to \(n\). However, we believe the conjecture might be true, when imposing some extra conditions on the auxiliary \(n'\) allowed to be used. In particular, the paper shows how subtle the notion of malleability is. Cited in 1 Document MSC: 11A07 Congruences; primitive roots; residue systems 11A51 Factorization; primality 94A60 Cryptography Citations:Zbl 1172.94593 PDFBibTeX XMLCite \textit{L. Dieulefait} and \textit{J. Jiménez Urroz}, J. Comb. Number Theory 2, No. 2, 171--179 (2010; Zbl 1245.11007) Full Text: arXiv