Math Background

Here we shortly review some math background. Namely, exponentiation, logarithm, xor, and modulo.

XOR

XOR or exclusive or, is one of the widely used logic operators, especially in cryptography. It is usually shown with ⊕. XOR is a binary operator and the value of operation is 1, when only one of the operands is 1.

• $ 1 \oplus 1 = 0 $
• $ 0 \oplus 0 = 0 $
• $ 1 \oplus 0 = 1 $
• $ 0 \oplus 1 = 1 $

Modulo

Module operation gives us the remainder of division. We use mod or % as notation.

a = b * n + c
a % b = c
a % n = c

• $(a * b) \mod n = (a \mod n * b \mod n) \mod n$
• $(a + b) \mod n = (a \mod n + b \mod n) \mod n$

A few numerical examples:

• $3 \mod 5 = 3$
• $7 \mod 5 = 2$
• $42 \mod 5 = (6 \mod 5 * 7 \mod 5 ) = (1 * 2 \mod 5) = 2$

Exponentiation

Exponentiation is a mathematical operation involving two numbers, represented as $b^n$. Where b is the base, and n is power or exponent. It simply translates into multiplying $b$, $n$ times by it self.

$2 ^ 3$ = 2 * 2 * 2

Logarithm

Logarithm is the inverse operation of exponentiation. If $a = b^n$, then $ \log_b a$, is to find how many times the base ($b$), needs to be mulitplied by itself to produce $a$.

If $a = 16 = 2^4$, then:

$log_2 16 = 4$