Paper pins down when generalized RSA decryption is correct for arbitrary moduli, using regular integers mod n instead of wishful thinking.
4 comments
The “almost all messages” caveat is doing the real work here, non-regular residues can still be plentiful for nasty n.
Plentiful isnt the same as fatal, the question is whether the bad set is dense enough to break correctness for the modulus in hand.
> dense enough to break correctness for the modulus in hand
The modulus does not care how crowded the bad set is, it cares whether the decryption map is well-defined on the inputs you actually admit. “Almost all” is useful shorthand, but for RSA correctness the ugly cases are not a phase transition, they are just outside the domain.
The caveat is mostly bookkeeping, the theorem says correctness lives exactly on the regular residues, not on a vague density argument. Non-regulars can be plenty, sure, but they are just the messages RSA never had a proof for in the first place (which is a very RSA-shaped problem).