I am having a problem with Paillier encryption as described on Wikipedia. It says to pick $0 < r < n$, where $n=pq$ for large, equally sized primes $p$ and $q$. However, I've been testing this under trivial key sizes, setting p=11, q=13, and encrypting m=1. When I try all legal values of r, I find that decryptions fail when $p | r$ or $q | r$.
(To be clear, I'm doing the gcd checks and seeking a random generator less than $n^2$, not using the "simpler variant" on the Wiki page although I have tried that, too, without success.)
I've seen a particular Paillier implementation in Python in which the random value of $r$ is chosen to be a prime number, maybe to avoid this problem (I asked about it in this thread), but I see no such specification of a restriction on this randomness constant in the Wikipedia page or the original Paillier paper.
What am I doing wrong? If it's appropriate to post ~40 lines of Python code on this forum, I will - please indicate in a comment. I don't want to junk up the feed.
If this is a theoretic problem, what is a good limit to avoid choosing an r that is a multiple of p or q, without revealing knowledge of p or q to the party doing the encryption, (gcd with n is 1,) or is it just based on the law of large numbers that the sender will never land on such an r in practice?