So, Alice wants to use the RSA protocol and pays Cindy to generate the two (odd) primes p and w so she can use e=65537 and n=pw as her public key. Alice will then, upon receipt of p and w, privately, find d to use as her private key.
Cindy delivers p and w to Alice where p is prime, but she messes up and delivers a number w to Alice which is composite. This number w is the product of two (distinct) primes. (Assume (p,w)=1.) Alice doesn't realize that w is prime and under this assumption finds d. Therefore publishes her public key (65537,pw).
Amazingly, whenever a message M is sent to Alice using RSA using her public key and Alice uses her d, she always recovers the message M correctly! (Of course we assume that M and pw have no common factors).
How in the world is this possible?? What is the formula??
How do we prove that there is no such w that is 512 bits in size??
Edit: Also, how can we prove that two primes dividing w cannot have the same number of bits (in binary representation)?