Implementation of subquadratic GCD?

[Alexander Kruppa]

Décio Luiz Gazzoni Filho wrote:
> Hello,
> 
> I'm working on an application which requires taking GCD with huge (100k-digit) 
> integers. I believe the fastest GCD algorithm for integers in this range 
> would be the subquadratic recursive GCD. Is anyone aware of a freely 
> available implementation of this algorithm? (preferably in GMP, but anything 
> will do)
> 
> Décio
> 

Richard Crandall's giantint library (www.perfsci.com) has a subquadratic 
gcd. It's what George Woltman's Prime95 uses in P-1 factoring 
multi-million digit primality candidates. Afaik, the representation of 
integers in giantint and GMP is very similar (signed length, alloc and a 
string of machine words), so it should be easy to convert between them.

Alex