Difficult: I fail to see how the p-1 factoring algorithm is much more useful than Fermat's method. It seems you are still just picking a random number and making a wish. Also, it seems possible that, for p large enough, you can easily miss on picking a B such that p-1 divides B!. While it does also discuss HOW the algorithm works, it doesn't seem to mention much about WHY it works. If I just pick a=2, then it seems that I am hoping that the only small prime factor of p-1 is 2, since if p-1 had another small prime factor then it would not make sense for p-1 to divide a^B!. Maybe I'm just not thinking of it correctly because of the modulus?
Reflective: I'm really excited to learn about new methods of factoring numbers. Up until now, I had only know the conventional method, I had not even been aware of Fermat's method. The p-1 algorithm is confusing though. I do not see why it would work, and why you would not have more success just picking a random number. Also, does it only work on products of two primes, or can it work on products of more than two primes? I would imagine that we could make it work on products of more than one prime by picking larger bounds B to try to get the next largest prime, or simply trying to factor the next number after dividing by the first prime factor that we discover.
No comments:
Post a Comment