Posted by Jason Polak on 19. June 2018 · Write a comment · Categories: computer-science · Tags: , ,

Today we'll see a Python 3 implementation of the MD5 hashing algorithm, which was originally designed by Ron Rivest. Even though the MD5 algorithm has been compromised and is not longer secure, it is still in use today. For example, CS ISOs of Linux distributions often provide MD5 sums in addition to SHA256 sums.

There are a lot of C implementations of MD5 out there. However, they are not easy to read, especially for someone who is not used to C. Python 3, being closer to "math" rather than the computer, reads more like a definition of the algorithm. Of course, the Python implementation is slower than the C one.

This Python implementation is ideal for experimenting with MD5 and learning about it. The code I give below is not the most compact possible, but I believe it is easy to understand.
More »

Posted by Jason Polak on 01. June 2018 · Write a comment · Categories: computer-science · Tags: ,

This is a continuation of the OpenMP tutorial. Last time we wrote the following program:

It gives a proof that the number $N = 770948605618065977$ is prime by testing all the possible factors up to the integer part of the square root of $N$. To recap, this program creates two threads and tests half the possible factors on one thread, and half the possible factors on another thread. Wouldn't it be nice to have the program split the loop work up automatically instead of having to do it manually?
More »

Posted by Jason Polak on 30. May 2018 · Write a comment · Categories: computer-science · Tags: , , , ,

Today, I'll give you a simple and practical example of using OpenMP with gcc. What's OpenMP? It's a C/C++/Fortran library for writing multithreaded applications. What's that? Most computers these days have multiple cores so that multiple tasks can be done in parallel. With multiple cores, you can edit pictures and listen to music at the same time without a noticeable slowdown. The intensive editing computations and music decoding happen on separate cores. It's a little more complicated than that, but that's the basic idea.

If your computer has multiple cores, it can use them in a single program. That's where OpenMP comes in. For concreteness, let's say you want to test whether the number 770948605618065977 is prime. If you're sane you'd just use the Miller-Rabin test like we've been discussing on this blog, and be happy with a 99.99999% probability that the number is prime. However, let's say you want to prove this number prime by trying all the numbers up to the integer part of its square root, which is 878036790.

Here is a minimal C program to do this:
More »

Posted by Jason Polak on 18. February 2018 · Write a comment · Categories: computer-science · Tags: , ,

Let's look at Python's map function. What does this function do? Here is the syntax:

It takes a function called function and applies it to each element of iterable, returning the result as an iterable. For example:

The output of this program is:

More »

Posted by Jason Polak on 18. February 2018 · 2 comments · Categories: computer-science · Tags: , ,

Let's assume you have a polynomial over a finite field $\F_q$, defined in Sage. How can you tell whether it's a permutation polynomial? That is, when is the corresponding function $\F_q\to\F_q$ bijective?

This is how you might have a polynomial over $\F_q$ defined in Sage:

Here, the variable $x$ refers the element $x$ in the isomorphism $\F_q \cong \F_p[x]/\alpha(x)$ and $t$ is the variable in the polynomial ring $\F_q[t]$. Is $f$ a permutation polynomial? That of course depends on what $q$ is.
More »

Posted by Jason Polak on 13. February 2016 · Write a comment · Categories: computer-science

Author: Feng-Hsiung Hsu
Title: Behind Deep Blue: Building the Computer that Defeated the World Chess Champion

Photo by Jason Polak (A chess set I received when I was sixteen).

Photo by Jason Polak (A chess set I received when I was sixteen).

I love battles of skill and stories of seemingly impossible goals. That's the stuff of Bruce Lee, the Riemann hypothesis, and getting a tenure-track position. And then there's the computer chess problem: create a machine that can beat the world chess champion at tournament-time chess. This happened nearly twenty years ago, when Deep Blue defeated Garry Kasparov in a six-game match. This is the story told in Behind Deep Blue by Feng-Hsiung Hsu.

Today in 2016, far more advanced chess programs like Stockfish running on a laptop can easily vanquish world-class human players. Hsu's book however, has lost none of its intrigue or charm. Of course, there are several books written about Deep Blue, many of them chess analyses. Behind Deep Blue however is not a chess book. After all, if it were I wouldn't be reviewing it on a mathematics blog. Instead, Behind Deep Blue is a story about a bunch of guys solving a computer science and hardware engineering problem.
More »