[QUOTE=jasonp;167940]According to wikipedia, CFRAC was translated into a computer-friendly algorithm around 1975, so that may have been the most advanced algorithm available. Without a lot of tweaks, even CFRAC would huff and puff trying to factor a C31.[/QUOTE]Resurrecting this old thread...

Just downloaded a copy of [B]The Aliquot Project: [I]An Application of Job Chaining to Number Theoretic Computing[/I][/B][SUP]1[/SUP] by M. C. Wunderlich.

This sheds a little light on what he was using back then. After some discussion of the properties of Aliquot Sequences, he talks about a framework that was being built to automate the production of sequences. Hardware is given as being an IBM 360/70[sup]2[/sup] computer running HASP. (A time of <12 seconds to generate an [TEX]N\pm1[/TEX] primality proof for numbers less than 40 digits on such a system is given.)

In the main program, trial division was used (looks like maybe 1M as an upper bound). If the trial division was unsuccessful, the composite was submitted to an external factoring utility. If a quick method (maybe Pollard's Monte Carlo method) could not factor it, another, longer, job was submitted to factor it.[quote=Wunderlich]We already have a very successful version of Brillhart's continued fraction program which submits a sequence of small jobs each of which generates a collection of factored quadratic residues. When a large enough collection of factored residues are generated, a 1 minute program is submitted which completes the factorization proces by doing a Gaussian elimination on a very large (360,000 bytes) 0-1 matrix.[/quote]One example is given in the article:[quote=Wunderlich]One of our 36 digit factorizations took from Wednesday afternoon to Saturday morning to complete its work, going trhough a chain of 10 twenty minute jobs.[/quote]So it looks like ~3 hours wall time to factor a 36 digit number, though it probably would have been impossible to wangle 3 consecutive hours of time on a heavily used computer. So the wait must have been almost unbearable: 3 hours to do 36 digits, but having it spread out over 3 days. Talk about suspense!

-----------

[SUP]1[/SUP][I]Proceedings of the 1976 ACM Symposium on Symbolic and Algrebraic Computing.[/I] Unfortunately, ACM has not opened up their article archives yet. Luckily I had $15 sitting unused on a gift card......might as well burn it on something interesting.

[sup]2[/sup]A nice description of a 360/70 is given [URL="http://www.bobseidel.com/columns/history4.html"]here[/URL].