It immediately comes to mind that it should now be easy to get multivariate factoring for ginac. Just use NTL and those parts of Factory that are not already in ginac. Although there is another possibility (add Factory only) the Factory source says itself that NTL is faster. However, I see a third plan: if you already accept including another library then why not libpari? Univariate factoring in Pari is as fast as NTL, both use van Hoeij, and Pari has much more for the work, starting with a mature integer factoring package etc. All three mentioned packages are distributed under GPL.
So, assuming I have summarized the situation correctly, which way?
After experiencing both for integration inside giac, I would recommend NTL over pari, because pari is a C library that may cause conflict names (at compile time but also at link time). Also I don't know if NTL supports threads, but I'm sure pari does not. I did not try direct integration of singular yet, I'm planning to do it for Groebner basis, but if it gives better performance for factorization, I will also use it for that purpose. Another solution I would recommend (but I'm not impartial of course:-)) would be to build a GiNaC::ex to giac::gen converter, that would bring to GiNaC multivariate factorization as well as all the other mathematical functionnalities of giac (e.g. symbolic integration, etc.). That would factor(!) the cost of integration of advanced math functionnalities over one library.
My other question is a plea: does anyone of you have a good overview over what is to do algorithmically to get multivariate factoring, given an existing univariate implementation? I'm not at a university but I'd shell out the EUR 8 at Subito for a copy of a good introductory or review article. So, please send refs/results to me or to the list.
If you can read French, giac multivariate factorization algorithm is documented on my webpage. First make some random evaluation to see if the 1-variable evaluated polynomial is irreducible, if not choose a variable so that the degree is the smallest possible, then evaluate other variables one by one and reconstruct the factorization using symmetric representation like for the heuristic GCD (this multivariate factorization is relatively easy to program once you have univariate factorization). There are probably more efficient algorithms on the market, I'd also be happy if someone has good references. Bernard Parisse www-fourier.ujf-grenoble.fr/~parisse