Computation over Zp in Python

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.

This entry was posted in Math, Programming, Python and tagged , , . Bookmark the permalink.

2 Responses to Computation over Zp in Python

  1. Ofir says:

    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.

  2. lorg says:

    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/ )