In practice, the RSA algorithm has proven to be effective, as long as it is implemented correctly. We give a few possible implementation mistakes in the Exercises. Here are a few other potential difficulties. For more about attacks on RSA, see [Boneh].
Let have digits. If we know the first , or the last , digits of , we can efficiently factor .
In other words, if and have 300 digits, and we know the first 150 digits, or the last 150 digits, of , then we can factor . Therefore, if we choose a random starting point to choose our prime , the method should be such that a large amount of is not predictable. For example, suppose we take a random 150-digit number and test numbers of the form