Hmm, this is interesting. Singular may be frightening for factoring with some big bad examples, but it seems we've got some work to do for the small cases. sage: R.<y,z>=QQ[] # singular sage: r=y^37-1 sage: timeit r.factor() 1000 loops, best of 3: 1.04 ms per loop sage: S.<x>=ZZ[] # NTL, but the factoring code converts to pari. sage: s=x^37-1 sage: timeit s.factor() 100 loops, best of 3: 5.2 ms per loop The moral might be: conversions are costly (but we already knew that).
I've written a factoring routine which implements the idea which was floated by William from the gcdheu algorithm. A paper of Fateman simply calls it Kronecker's trick -- specialize at a large number and factor the resulting integer or polynomial of lower degree. The whole thing hinges around an appropriate definition of "large" which I can't find or testing after the fact that we chose large enough. So far, my mpoly over ZZ factoring code reduces to a univariate and factors that. Profiling indicates that the univariate factoring is a significant hunk of my time -- I guess that means my all-python book-keeping is respectable. Oh, and my kroneckers trick algorithm for my special case absolutely clobbers singular, but I don't think that is really a great shock. -- Joel --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
