Lately I’ve been working a lot on my Algebric Structures homework. One of the reasons I don’t blog as much as I should. While working on my homework, I had to factor some polynomials over Z5 – the field containing the numbers {0,1,2,3,4}. The trick was that given a 4th degree polynomial without any roots, you could only factor it to two 2nd degree polynomials.
That turns out not to be that hard, but a bit of work – especially if you dislike just computing values. So I wrote a simple script to solve this little problem for me. While writing that script, I saw that it could be really fun to write a general Zp class. So naturally, I fired Google up, and tried looking for existing implementations. I didn’t find any (except some python implementations of many number thoery algorithms). Being quite a small amount of work, I hacked up something. After finishing with it, I wrote a polynomial class that can accept any given “number class”. There is actually a public implementation of real valued polynomials in SciPy, but not for integer valued or Zp-valued polynomials. After some more work my polynomial class was also finished. I actually used that class for some computations later on.
I added polynomial division, just for the heck of it, even though I didn’t use it. I hope this little script will be useful to someone.
2 replies on “Computation over Zp in Python”
hmmmmm I know this is a really old post, but are you familiar with http://www.sagemath.org/ ?
It’s essentially a python-based matlab.
Yes, I know of it.
At the time I think I also knew of it already but didn’t use it yet.
These days I also don’t use it though, as I haven’t needed it, except one time. At that time, I was made aware of sage’s capabilities only after solving the problem.
(Actually, by a comment to this blog on this post: http://www.algorithm.co.il/blogs/index.php/programming/python/computing-large-determinants-in-python/ )