Factorization

[Richard B. Kreckel]

Hi there,

On Thu, 5 Jul 2001, Wolfgang Abele wrote:
> can you tell me what's the current situation regarding polynomial 
> factorization in GiNaC? According to your wishlist, it's still missing, but 
> I've just read some mails in this list saying that some people are working on 
> the task.

Not that I knew of...

> I'm a student of mathematics, and my diploma thesis is about polynomial 
> factorization. I'm interested in both factorization in Z[x] and algebraic 
> extensions, and I wonder if I could implement some algorithms or contribute 
> to any ongoing projects.

Factorization in Z[x] is something that would be somewhat outside the
normal GiNaC usage.  As you have already found out there is no support for
univariate polynomials over, say, Z.  The reason for this is threefold:
1) for our physics applications here this is uninteresting,
2) we needed the more general expressions anyways and
3) implementation-wise this is the more trivial case anyway and already
   cleanly implemented in other libraries, CLN for instance.
However, factorization in GiNaC would become really interesting as soon as
one considers all the lifting up to multivariate polynomials over Z (and
maybe algebraic extensions but I think these are not the main difficulty).  
If this is in any way tractable, I would suggest not investing too much
time into factorization over Zp[x] by maybe implementing this in CLN --
which by the way would be a good place for factorization.  Instead, maybe
what should be done is use Victor Shoup's GPL'ed library NTL which seems
to be the powerhorse in this field.

But then again, I am not an expert in this field and would be glad to be
convinced otherwise.  Suggestions?

> By the way, I've found out how to declare a polynomial ring over modular 
> integers in CLN, so I don't need an example any more.

Cool!

Regards
    -richy.
-- 
Richard Kreckel
<Richard.Kreckel at Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>