On Jan 21, 1:39 am, William Stein <[email protected]> wrote: > On Tue, Jan 20, 2009 at 9:59 PM, [email protected] <[email protected]> wrote: > > > Hi, > > I want compute gcd(f,g), where f and g are polynomials and their > > degree are huge, e.g. deg(f) is about 2^300. > > I looked through the Sage reference manual, and learned that NTL > > is a library of fast arithmetic with polynomials. But is seems that > > the degree of my polynomial is too large, can anyone help me? Thanks > > Are your polynomials very sparse or dense? Just to store a degree > 2^300 dense polynomial would take 2^300 memory locations, but modern > computers have < 2^64 memory locations. If the polynomial is very > sparse, use symbolics: > > sage: var('x',ns=1) > x > sage: f = (x^(2^300)+x +1) > sage: g = (x^(2^300) - x) > sage: expand(f*g) > x^4074071952668972172536891376818756322102936787331872501272280898708762599526673412366794752 > + > x^2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376 > - x^2 - x
Unfortunately, this seems not to work: sage: gcd(f, g) --------------------------------------------------------------------------- OverflowError Traceback (most recent call last) ... OverflowError: long int too large to convert to int I'd be surprised if Sage had any code to do this straightforwardly; I think you'll have to write your own code. Just running the standard gcd algorithm won't work; it would take at least 2^300 steps, which is a "longer than the life of the universe" timeframe. Perhaps some sort of multimodular algorithm could work, where you take advantage of x^p=x (mod p) to bring the exponents down into a reasonable range. (I'm not sure how you recombine the outputs, though, especially if you want a provably correct result.) Carl --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
