"Lehmer sieves were very fast, in one particular case factoring 2^93 + 1 in 3 seconds."
Impressive. I wondered how fast my computer could do it. Here's the GNU coreutils factor:
$ time factor 9903520314283042199192993793
9903520314283042199192993793: 3 3 529510939 715827883 2903110321
real 0m0.007s
user 0m0.004s
sys 0m0.000s
Still impressive. This led me down factor's documentation to the Pollard Rho algorithm:
http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm