Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA For prime number generation, one can use a probabilistic prime number generation algorithm like the Miller–Rabin primality test that will yield a composite as a probable prime with probability $\frac{1}{4^r}$ for $r$ rounds. If we use $r=50$, this has probablity $2^{-100}$. This is enough to believe that it is prime due to the high probability, if the collective power of Bitcoin miners is not searching a candidate, we will not see one around.
What if we want to make sure that it is 100%? We can use the deterministic AKS primality test and its faster variants to see that it is prime or it was a pseudoprime for the Miller-Rabin. AKS primality test, however, is very slow, and that is why we use probabilistic methods.
Now, instead of AKS, we want a faster approach and use it in the RSA cryptosystem to encrypt and decrypt a message. If everything works we will assume it is prime (should we?)!
Take a well-known prime like Fermat or Mersenne primes call it $p$ and the pseudo-prime (a real one can be found if we use fewer rounds but assume that we found one with 50 rounds) and call it $\bar{p}$. Construct the RSA as usual with the exception that instead of choosing firstly $e$ then finding primes, choose a suitable $e$.

$n = p \cdot\bar{p}$
$\varphi{(n)} = (p-1)(\bar{p}-1)$, (actually we can use $\lambda{(n)}$)
find $e$ such that $\gcd(e, \varphi(n)) = 1$
find $d \equiv e^{-1} \pmod{\varphi(n)}$

and the rest is textbook RSA encryption and decryption.
Question(s):

We expect that the encryption will fail since the incorrect $\varphi(n)$. Is there a pseudo message that correctly encrypts and decrypts under this pseudoprime $\bar{p}$?

If, so, how we can find one?
If, so, what is the probability of the pseudo messages?
We expect that the encryption will fail since the incorrect $\varphi(n)$.


Not always; for example, consider the case $p=31$ (a Mersenne prime) and $\bar{p} = 561 = 3 \times 11 \times 17$.  We'll set $e = 13$ and $d = e^{-1} \bmod 30 \times 560 = 3877$.
Then, if we pick a random message $m=2$, then $2^e \bmod n = 8192$, and $8192^{3877} \bmod n = 2$; encryption and decryption works just fine.  Actually, it turns out that any value $m$ will encrypt and decrypt properly with this particular $n, e, d$ set.
Lets try it again with another random example; this time we'll pick a Fermat prime $p=17$ and an arbitrary $\bar{p} = 91 = 7 \times 13$, and so $n= 1547$.  This time, we'll use $\lambda(n) = (p-1)(\bar{p}-1) / \gcd( p-1, \bar{p}-1 )= 720$; we'll pick $e=7$ and so $d=e^{-1} \bmod \lambda(n) = 103$.  Again, if we pick a random message (we'll try $m=3$ this time, we have $3^e \bmod n = 640$ and $640^d \bmod n = 3$.  And, again, any $m$ will encrypt and decrypt properly with this particular $n, e, d$ set.
So, how did this work?  Did I just pick these examples at random?  Is this always true of Fermat and Mersenne primes?  Well, no, for this trick, I selected my $\hat{p}$ values carefully, and most everything else was arbitrary.
In the first case, I selected $\hat{p}$ to be a Carmichael number, that is, a composite number such that $\lambda(\hat{p})$ is a factor of $\hat{p}-1$.  It turns out that a Carmichael number acts just like a prime as far as RSA is concerned; any $p$ (relatively prime to $\hat{p}$ would make it work).
In the second case, I selected a $\hat{p}$ that wasn't a Carmichael number (561 happens to be the smallest), but instead it is something we may call a &quot;semicarmichael number&quot; (terminology I just made up, so don't bother googling it); it has the property that $\lambda(\hat{p})$ is a factor of $2(\hat{p}-1)$.  Now, these numbers won't always work within RSA, however it does work if either $p \equiv 1 \bmod 2^{k+1}$ (where $2^k$ is the largest power of 2 which is a divisor of $\hat{p}-1$), or alternatively you use the $\phi(n)$ relation of $e, d$ (rather than the $\lambda(n)$ relation - for primes and Carmichael numbers, it doesn't matter - for semicarmichael numbers, it does).
So, what does this stage magic trick relate to your question:

If, so, what is the probability of the pseudo messages?

Higher than you'd expect, if you did a number of rounds of Fermat or Miller-Rabin beforehand.  It turns out that Carmichael numbers will always fool Fermat (unless you happen to pick a generator that's not relatively prime to the Carmichael number), and semicarmichael numbers will fool Fermat half the time.  And, both these numbers have good probability of fooling Miller-Rabin (obviously $&lt; 1/4$, however sometimes not much less).  Hence, while Carmichael and semicarmichael numbers are rare, if you have a composite number that fools several rounds of Fermat or MR, the probability you started with such a number is pretty good.