Implementation of subquadratic GCD?

Alexander Kruppa alexander.kruppa at someplace
Wed Dec 1 16:45:54 CET 2004

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 ( 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.


More information about the gmp-discuss mailing list