Miller-Rabin-Test

This is an improved version of the fermats primality test, which takes fermat liar into account.

Works with x\geq3:

Choose a random number a \in \{2,\dots x-,\}
Check if a is co-prime to x. If not x is not a prime number.
Calculate a odd number d, which solves the following equation: x-1 = d \cdot 2^{j}
Test if x is meets the following conditions; if not a is a fermat witness that x is a composite number
- a^{d} \mod x = 1
- a^{d \cdot 2^{r}} \mod x = x - 1 for r \in \{0,\dots j-1 \}