Section 6.4.1, Due October 25

Difficult: It mentions on page 185 that the easy way to pick good numbers for this method is to look at numbers of the form root{in}+j for small j, which makes sense as we are looking to cough out powers of small primes. This seems to be pretty reliable, but we have discussed how none of the current methods are sure-fire quick ways to factor a large prime. What is the trouble with this one? Obviously, we have the possibility every time of finding only multiples of n, but it seems that we could just choose more numbers to try and we will get it eventually, and it doesn't seem to take too much time to compute one more row of numbers. Does this method fail if p-1 and q-1 have no small prime factors? I don't see how that would mess things up. Is it possible that for a given n there exists no possible x and y that fit the hypothesis of the Basic Principle? It seems like for large n, there should always be such x and y.

Reflective: This method does not seem difficult or to take much time (except maybe by hand since we are working with large numbers). Clearly it must take more than I am imagining. It is interesting that they can now regularly factor numbers of more than 200 digits easily, but then we can still exponentially increase the difficulty by adding more digits so I suppose that is not terribly encouraging. I noticed we were not required to read section 6.4.2, are these methods not as useful, or not as simple?