The easiest way to root an Android phone on linux is to use Heimdall. Heimdall is an open source program to flash Android on Samsung Galaxy devices.
Heimdall is available as a binary executable for many platforms, including Debian. Unfortunately, since I use Fedora, I had to compile the code from scratch.
First install all the needed tools.