The premise "_we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy_" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see [FIPS 186-4 appendix B.3.2][1]). We can even practically prove (or disprove) the primality of an arbitrary 2048-bit integer, using a method pointed in [comment][2]: Daniel J. Bernstein, [_Proving primality in essentially quartic random time_][3], in Mathematics of Computation 76 (2007), 389–403 (which is a randomized test giving a certainty; only the time it takes to reach certainty depends on the particular randomness used). However this is complex, and practical cryptography is happy with a (faster) probabilistic primality test. Notice that 64 rounds of [Miller-Rabin test][4] against an integer one has randomly _drawn_ (which is the case in RSA key generation), rather than _received_ from a potentially hostile party, are way overkill to rule out compositeness with residual odds less than $2^{-128}$; 4 rounds are more than enough, see [FIPS 186-4 table C-2][5], with justification in [appendix F][6] and its reference: Ivan Damgard, Peter Landrock, and Carl Pomerance, [_Average case error estimates for the strong probable prime test_][7], in Mathematics of Computation 61 (1993), 177–194. --- If we _accidentally_ try to perform RSA with one of $p$ or $q$ composite, the usual formulas $\varphi(p\cdot q)=(p-1)\cdot(q-1)$ or $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ will lead to incorrect value, and with overwhelming odds decryption or signature verification will fail on the first real use (assuming a random message or proper padding is used). In a PKI context, the verification by the certification authority of the [public-key certification request][8] (which is customarily self-signed) will almost certainly fail. A successful use of RSA constitutes a powerful primality test of $p$ and $q$ (about as powerful as a [Fermat test][9] with a random witness, that is less powerful than a [Miller-Rabin][10] test, but still very effective). However (just as all practical primality tests for large integers), it gives an indication of compositeness, but does not reveal a previously unknown factor; that's where the reasoning/intuition in the question breaks. [1]: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=62 [2]: http://crypto.stackexchange.com/q/25878/555#comment59638_25878 [3]: http://cr.yp.to/papers.html#quartic [4]: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test [5]: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=80 [6]: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=126 [7]: https://math.dartmouth.edu/~carlp/PDF/paper88.pdf [8]: http://en.wikipedia.org/wiki/Certificate_signing_request [9]: http://en.wikipedia.org/wiki/Fermat_primality_test [10]: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test