Categories

## Using zpint in Cryptography Homework

Originally, I wrote zpint to help me with my algebric structures homework. For those not familiar with it, it allows you to do computations modulo p the same way you do for ints. Not surprisingly, I found myself using it in my cryptography homework as well. At first I used it for trying to breaking the Hill Cipher. Then for some computations such as using the Chinese Remainder Theorem to solve equations, or to compute RSA values. Last it was for checking if algorithms I wrote were correct.

Usually I prefer to write a script than do all the computations by hand, even if writing the script is more work. Mostly because it is work I enjoy more. This time I had a script ready. I improved it a little bit during the semester, and it is still available. It is certainly not the fastest way to compute, but it is a fast way of doing computations.

Categories

## 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.