Hi John, Yes those are tiny polynomials. The way NTL works is to compute the content of both polynomials and divide out by that, compute the gcd of the contents, break up one prime at a time and compute the gcd mod p. After each recombination (it's all done "in place") it checks to see if the gcd computed divides both the original polynomials.
It's impossible to say whether that is going to be optimal or whether the subresultant method of pari would be optimal. You can give it a try. In your case, if you already know all the roots, you could try the GCDHEU method. It's trivial to implement. See http://www.inf.ethz.ch/personal/gonnet/CAII/HeuristicAlgorithms/node1.html The basic idea is to substitute a value n (chosen to be sufficiently large) into your polynomials, then take the gcd of the resulting integers (this will be exceedingly fast now since the latest GMP uses very good algorithms), then split the resulting integer up into polynomial coefficients. GCDHEU is probably the perfect algorithm to use since your polynomials are tiny and you already know the roots. Bill. On 14 Sep, 03:11, John Voight <[EMAIL PROTECTED]> wrote: > Hi Bill, > > Thanks for your messages--it certainly is an interesting problem when > viewed in context. > > For me, my polynomials are tiny: small degree (<=11) and very small > coefficients. Moreover, I already have computed the roots to some > numerical precision and only call this when there appears to be a > coincidence of roots, and so I have good reason to believe that the > polynomials have a common factor. It seems like the best way to > verify this (without actually computing the gcd over Z!) would be to > use a modular method--but I realize that in practice, resultant > methods are often used and have certain advantages. > > I'm not sure I've added much to your discussion, but anyway, thanks > for looking into this. > > Yours, > > John Voight > Assistant Professor of Mathematics > University of Vermont > [EMAIL PROTECTED] > [EMAIL PROTECTED]://www.cems.uvm.edu/~voight/ --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
