# FCS: Assignment 4. Math
Salavat Dinmukhametov
1. 5
2. 13
3. 6
4. 00100110, 22
5. 01100111, 55
## Task 1
a) 8, 15, 6 is not prime numbers, so first of all lets simplify them.
a = 3⁷\* 2⁹ \* 5⁶
b = 2³ \* 3⁵ \* 7⁴ \* 11

GCD(n, m) = p₁^{min(d₁, e₁)} ... p_k^{min(d_k, e_k)}
LCM(n, m) = p₁^{max(d₁, e₁)} ... p_k^{max(d_k, e_k)}

So , GCD(a, b) = 2³ \* 3⁵ = 1944
LCM(n, m) = 2⁹ \* 3⁷ \* 5⁶ \* 7⁴ \* 11 = 4,62086856×10¹⁴

b) 7¹²³⁴ mod 11
c ≡ (a \* b) mod m
c ≡ (a \* (b (mod m))) mod m
So, I wrote simple python program

## Task 2
gcd(26, 91)

| Step | Pair | Reminder | Linear Comb |
| -------- | -------- | -------- | ---|
| 1 | 91 26 | 13 | 91 = 26\*3 + 13
| 2 | 26 13 | 0 | 26 = 13 \* 2
Answer = 13

## Task 3
Next five states of the LFSR:
1) | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| - | - | - | - | - | - | - | - | - |
2) | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
3) | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
4) | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
5) | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
6) | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |

Previous four states
1) | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| - | - | - | - | - | - | - | - | - |
2) | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
3) | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
4) | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
5) | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |

if we xor 1111 with 1110, where 1110 is first 4 bits in 4 state, result is 0001.
Then lets xor with 0111, is 4 state, 0110.
See table below

| step | plaintext | key | result |
| -------- | -------- | -------- | - |
| 1 | 1111 | 1110| 0001
| 2 | 0001 | 0111| 0110
| 3 | 0110 | 1011| 1101
| 4 | 1101 | 0101| 1000

Answer: 1000