# Math Foundations

## Some terminology

- **plaintext**: original message needed to be transmitted.
- **ciphertext**: the encrypted data which is "unreadable".
- **cipher**: the math or algorithms responsible for turning plaintext into ciphertext.
- Stream cipher
- Block cipher
- **Encryption**: process of {plaintext > ciphertext}
- **Decrpytion**: process of {ciphertext > plaintext}
- **Secret Key**: an input for Encryption/ Decryption.

- W -> 22 -> might be $22 + 29 * 1 (or 29 * 2, 29 * 3) = 51, 80, 109, 138, 167...$ and find the number that can divide 10 (since our secret key is $10$).
- So the algorithm can be:

cipher = 22 # the char we get in ciphertext 
result = []
# the range of the original number is from 0 * 10 to 28 * 10 = 0 ~ 280
i = 0

while (True):
	guess = 22 + 29 * i
	if (guess % 10 == 0):
		result.append(guess / 10)
	i += 1;
	if (i >= 28):
		break

print(result)

## Modulo (mod)
> the definition of remainder is `non-negative integer`.

### Integer mod n
> $a \mod n \in \set{ 0,1,2,3...,n-1 }$, if a is an integer
- for example: $integers \mod 7 \in \set{0,1,...,6}$
- $-1 \mod 7 = -1 + 7 = 6$ (the modulo would always be in the set$\set{0,1,...,6}$, and the remainder should always be **non-negative integer**)
- $10 \mod 7 \equiv 17 \mod 7 \equiv 24 \mod 7 \equiv 3$

### Inverse
> By definition, if $a$ is an integer $\mod n$ and $x$ is its inverse, then they satisfy the equation:

$$
ax \equiv 1 \pmod n
$$

### Find Inverses
How to prove if an integer has an inverse?

Let $a \in \text{integer} \pmod n$ number system.

- `a` will have an inverse iff `gcd(a, n) = 1`
- if `n` is a prime number, then **all numbers** `a` **except 0, will have an inverse**.

### Proof:
> `a` will have an inverse iff `gcd(a, n) = 1`

if `a` has a inverse `x` => `gcd(a, n) = 1`

$$
\begin{align}
ax &= 1 \pmod n
\\ ax &= 1 + k \times n
\\ ax - kn &= 1
\\ gcd(a,n) &= 1 (\text{by Bézout's identity})
\end{align}
$$

> Bézout's identity — Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. Moreover, the integers of the form az + bt are exactly the multiples of d. - [wikipedia](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity)

And reverse way is the same using Bézout's identity.

### Reminder
> if `n` is a **prime number**, them all numbers $a \in {1, ..., n}$ will have an inverse in the number system $a \mod n$.

According to the above description: `a` will have an inverse iff `gcd(a, n) = 1`. since for any $a \in {1, ..., n-1}$, $a$ and $n$ are coprime, $a$ has a inverse.

---

But the above only tell us that there's an inverse but does not tell us how to calculate it. There's algorithm that can help us to calculate this. But before this, `Homomorphism Theorem` is introduced.

## Homomorphism Theorum (HT)

`*` represent an operation (not multiplication , either `+`, `-`, `*`
$$
(a * b) \% n = ((a \% n * (b \% n)) \% n
$$

**example**:
$$3^5 \mod 7$$
1. $3^2 = 9$
2. $3^4 = 9^2 = 81$
3. $3^5 = 3 * 3^4 = 3 * 81 = 243$
4. thus, $3^5 \mod 7 = 243 \mod 7 = 5$

Yet this algorithm is kinda slow/ not effecient:

Alternative:
1. $3^2 \mod 7 = 2$
2. $3^4 \mod 7 = 2 * 2 \mod 7 = 4$
3. thus, $3^5 \mod 7 = 3 * 4 \mod 7 = 5$

**Divisible by 9**:
If a integer `a` is divisible by 9, then we can add all digits, then the sum is also divisible by 9.

`1234566` => `(1+2+3+4+5+6+6) = 27 = 9 * 3`

Proof using HT:
let the number `a` is $\sum 10^{i} \times a_{i}$

| i: | n | n-1 | ... | 1 | 0 |
| ----- | -------- | ---------- | --- | -------- |:-------- |
| a_i | $a_{n}$ | $a_{n-1}$ | | $a_{1}$ | $a_{0}$ |
| digit | $10^{n}$ | $10^{n-1}$ | | $10^{1}$ | $10^{0}$ |

now that:
$$
\begin{align}
a \% 9 &= (\sum 10^{i} \times a_{i}) \% 9
\\ &= \sum (a_i \% 9) \times (10 \% 9)^{i}
\\ &= \sum (a_i \% 9) \times 1
\end{align}
$$

This means the result of $a \% 9$ is equal to $\sum (a_i \% 9)$, which means we can use this result to calculate in $a \% 9$.

**Exercise**:
calculate: $(100 \ {digit}) ^ {100 \ {digit}} \mod 100 \ {digit}$

## Inverse Algorithm and Division
The inverse algorithm solves the equation:
*find $x$, given $a$ and $n$ that satisfies*:

$$
ax \equiv 1 \pmod n
$$

The **inverse of $a$ is $b$** and this gives us a way to do division:

$$
a / b \pmod n \equiv a * b^{-1} \pmod n
$$

yet how to find the Inverse?
1. $n * x \equiv n \pmod n$ -> $E_1$
2. $a * x \equiv 1 \pmod n$ -> $E_2$
3. $(n-a) * x \equiv n - 1 \pmod n$ -> $E_1 - E_2 = E_3$
1. if the number on the right is negative, add $n$.
4. Discard the equation with the largest number in front of $x$, and repeat
5. Stop when the number in front of $x$ = 1

Example

Calculate the inverse `x` of `8 \mod 13`

$$
\begin{align}
13x &= 13 \pmod 13
\\ 8x &= 1 \pmod 13
\\ 5x &= 12 \pmod 13
\\ 3x &= -11 = 2 \pmod 13
\\ 2x &= 10 \pmod 13
\\ x &= -8 = 5 (\text{stop})
\end{align}
$$

check:

if x = 5
$8 \times 5 = 40$, $40 \% 13 = 1$ => $8 \times 5 = 1 \pmod 13$ => 5 is inverse of $8 \pmod 13$.

## Quiz
1. Calculate $5^7 \mod 11$ by hand using `repeated squaring` and the `HT`.Verify that the calculations would be much harder if you left the $\mod 11$ calculation to the end.

hand calculation:
$$
\begin{align}
5^7 \mod 11
\\ 125 \times 625 \mod 11
\\ 78125 \mod 11
\\ 78125 = 11 \times 7102 + 3
\\ 78125 \mod 11 = 3
\end{align}
$$

HT:
$$
\begin{align}
5^7 = 5^2 \times 5^2 \times 5^2 \times 5 \pmod{11}
\\ (5^2 \mod 11 = 3)
\\ 5^7 \mod 11 &= (3^3 \times 5) \mod 11
\\ &= (27 \times 5) \mod 11
\\ &= (5 \times 5) \mod 11
\\ &= 25 \mod 11
\\ &= 3
\end{align}
$$

2. Calculate $1/8 \mod 11$ (the inverse of 8) by hand using equation subtracting algorithm. Using your result to calculate $5/8 \mode 11$

$$
\begin{align}
11x \equiv 11 \pmod{11}
\\ 8x \equiv 1 \pmod{11}
\\ 3x \equiv 10 \pmod{11}
\\ 5x \equiv -9 \equiv 2 \pmod{11}
\\ 2x \equiv -8 \equiv 3 \pmod{11}
\\ x \equiv 7 \pmod{11}
\end{align}
$$

So the inverse of $8$ is $7$.

$$
8 \times 7 = 56 \pmod{11} = 1
$$

$$
5 \times 8^{-1} \pmod{11} = 5 \times 7 \pmod{11} = 35 \pmod{11} = 3
$$