Implementation of subquadratic GCD?
alexander.kruppa at someplace
Wed Dec 1 16:45:54 CET 2004
Décio Luiz Gazzoni Filho wrote:
> 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)
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.
More information about the gmp-discuss