Idempotent Factorizations of Square-Free Integers - Barry Fagin (Information, 2019)
We explore the class of positive integers n that admit idempotent factorizations <semantics> n = <mover accent="true"> p ¯ </mover> <mover accent="true"> q ¯ </mover> </semantics> such that <semantics> λ ( n ) ∣ ( <mover accent="true"> p ¯ </mover> − 1 ) ( <mover accent="true"> q ¯ </mover> − 1 ) </semantics> , where <semantics> λ </semantics> is the Carmichael lambda function. Idempotent factorizations with <semantics> <mover accent="true"> p ¯ </mover> </semantics> and <semantics> <mover accent="true"> q ¯ </mover> </semantics> prime have received the most attention due to their cryptographic advantages, but there are an infinite number of n with idempotent factorizations containing composite <semantics> <mover accent="true"> p ¯ </mover> </semantics> and/or <semantics> <mover accent="true"> q ¯ </mover> </semantics> . Idempotent factorizations are exactly those <semantics> <mover accent="true"> p ¯ </mover> </semantics> and <semantics> <mover accent="true"> q ¯ </mover> </semantics> that generate correctly functioning keys in the Rivest−Shamir−Adleman (RSA) 2-prime protocol with n as the modulus. While the resulting <semantics> <mover accent="true"> p ¯ </mover> </semantics> and <semantics> <mover accent="true"> q ¯ </mover> </semantics> have no cryptographic utility and therefore should never be employed in that capacity, idempotent factorizations warrant study in their own right as they live at the intersection of multiple hard problems in computer science and number theory. We present some analytical results here. We also demonstrate the existence of maximally idempotent integers, those n for which all bipartite factorizations are idempotent. We show how to construct them, and present preliminary results on their distribution.