commercial macsyma finished the gcd in 4,350 seconds. The arithmetic it uses (in CLOE, a CL implementation probably used by no one else) is not especially fast. RJF