In my previous post I considered an example of trying to find the two primes in the product 9980651 by satisfying equations (1) to (4) in part 3. So just how many possible solutions would we come up with if we went about this in a systematic way? As we saw there were 3 possible solutions in solving equation (1), and 10 each for equations (2), (3) and (4). This means that we would have at most 3x10x10x10=3000 potential solutions to search through until we found the pair of primes (2029,4919) that we were looking for.
How does this compare with, say, trial division? We know that the product consists of two primes each of which contain four decimal digits. Therefore a simple approach would be to divide 9980651 by all the integers between 1000 and 9999, a total of 9000 numbers. An alternative approach would be to divide by all the primes between 1000 and 9999, a total of 1061 such numbers. This is fewer than the 3000 pairs of solutions we would come up with but then you would have to calculate what these primes were in advance.
If we consider the products of primes which are 100 digits or more, then we can see that the challenge is enormous. For example, for RSA-220 there would be 3x10109 pairs of numbers to search through. Even if processing one pair corresponded to one instruction on a computer, then a computer operating at 1010 instructions per second could take 1092 years to find the right pair! So, unless this method can somehow be improved then it is not going to be a viable method for this challenge. In fact, it illustrates just how difficult it is to crack these products of large primes.
