Remainder

11 Feb 2024 in Study / Computer science on Remainder

Algorithm

Remainder (calculated result) is not changed regardless of the timing for calculation of remainder
That is, we have A, B, C, D, E (C is (A % E), D is (B % E))
- A + B ≡ C + D ≡ A + D ≡ C + B (mod E)
- A x B ≡ C x D ≡ A x D ≡ C x B (mod E)
- A - B ≡ C - D ≡ A - D ≡ C - B (mod E)
  - (object1 - object2) should not be negative
Ex
- (27 x 41 x 66) % 100
  - 27 x 41 = 1107 → 1107 % 100 = 7
  - 7 x 66 = 462 → 462 % 100 = 62
- (18 x (27 + 41 + 66)) % 10
  - sol1) (18 % 10) x (27 % 10 + 41 % 10 + 66 % 10) = 8 x (7 + 1 + 6) = 112 (still > 10) → 112 % 10 = 2
  - so12) (18 % 10) x (134 % 10) = 8 x 4 = 32 (still > 10) → 32 % 10 = 2

When we calculate the remainder of division, we should use other method
- A ÷ B ≡ C (mod D) : We wanna get C (< D)
- D should be prime number
General Calculation
- A ÷ B ≡ C (mod D) : We wanna get C (< D)
- If A % B == 0, just calculate division at first and calculate the remainder
  - ex) If A = 8, B = 2, D = 3 → 8 ÷ 2 ≡ 4 (mod 3) → C = 4
- Unless A % B == 0 (and then ÷ is different with normal calculation : This is only used for proving, so A % B == 0 should be satisfied in code problem)
  - A ÷ B ≡ C (mod D) → B x C ≡ A (mod D) → find desired C
  - ex) 9 ÷ 2 ≡ C (mod 11) → 2 x C ≡ 9 (mod 11) → C = 10
  - ex) 1 ÷ 6 ≡ C (mod 11) → 6 x C ≡ 1 (mod 11) → C = 2
Use modular inverse (모듈러 역수)
- Definition
  - A ÷ B ≡ C (mod D) ↔ A x B^-1 ≡ C (mod D) : B^-1 is modular inverse of B
  - We can find modular inverse if we use B x B^-1 ≡ 1 (mod D)
  - ex) 7 ÷ 3 ≡ C (mod 11)
    - 3 x B^-1 ≡ 1 (mod 11) → B^-1 = 4
    - 7 ÷ 3 ≡ C (mod 11) ↔ 7 x 4 ≡ C (mod 11) : C = 6
- Finding modular inverse easily
  - Use Fermat’s little theorem (페르마의 소정리) : B^D-1 ≡ 1 (mod D)
  - B x B^D-2 ≡ B^D-1 ≡ 1 ≡ B x B^-1
  - B x B^D-2 ≡ B x B^-1 ≡ 1
  - B^-1 = B^D-2
  - Consequently, A ÷ B ≡ C (mod D) ↔ A x B^D-2 ≡ C (mod D) : C = A x B^D-2 (mod D)

Code problems sometimes ask us to calculate the remainder of the result by a specific number (ex) if the result is too big)
If the final result is too big, it can be slow to calculate the remainder of the final result directly
Instead, we should calculate the remainder constantly and that remainder should be used to next calculation
- Addition, Subtraction, Multiplication : just calculate
- Division : calculate A x B^D-2 (mod D)
  - for code result being same with real result, the condition that A % B == 0 & D should be prime number should be satisfied
Example Problem1 This is the private repository where I can only review my notes
Repository

반복제곱법
When we calculate the remainder of division, we should calculate A x B^D-2 (mod D)
- If B^D-2 is too big, B^D-2 (mod D) is hard for calculation as well
- We can use iterative square method
Iterative Square Method
- ex) If we wanna calculate a²⁵ (mod D)
- a² (mod D) = a (mod D) x a (mod D)
- a⁴ (mod D) = a² (mod D) x a² (mod D)
- a⁸ (mod D) = a⁴ (mod D) x a⁴ (mod D)
- a¹⁶ (mod D) = a⁸ (mod D) x a⁸ (mod D)
- ….
- a²⁵ (mod D) = a¹⁶ (mod D) x a⁸ (mod D) x a¹ (mod D)
  - Use binary number (25 = 2⁴ + 2³ + 2⁰ = 11001)
  - if (b & (1 « i)) != 0:
    - i = 0 : (b & 1) != 0 → b = ?????1
    - i = 1 : (b & 10) != 0 → b = ????1?
    - i = 2 : (b & 100) != 0 → b = ???1??
    - i = 3 : (b & 1000) != 0 → b = ??1???
```
def it_pow(a, b, d):
  p = a
  answer = 1

  for i in range(11):         # If b < 2048 = 2 ** 11
      if (b & (1 << i)) != 0:
        answer = (answer * p) % d
      p = (p * p) % d

  return answer

def division(a, b, d):
  return (a * it_pow(b, d - 2, d)) % d
```
- In python, we just use pow(a, b, d) which already exists

book : 문제 해결을 위한 알고리즘 with 수학, p.275
Given Sender X & Receiver Y
Y prepares public key and private key
- Public key : integer n & e
- Private key : integer d which makes m^ed ≡ m (mod n) be satisfied regardless of m (m < n) (m is the data from sender X)
Y sends n & e to X
The data which X wanna send to Y are converted to integer m
- Receiver Y should find the value of m
In X, calculate m^e (mod n) (let the result be h)
X sends h to Y (Y should find what m is and What Y only knows is h, n, e, d)
m^e ≡ h (mod n) → m^ed ≡ h^d ≡ m (mod n) because of the definition of d
h^d ≡ m (mod n) → m = h^d (mod n) because of m < n
Consequently, Y can find m
but it is difficult for other users to find what m is because there is still no algorithm to find d only using public key

This is the private repository where I can only review my notes
Repository

Bioinformatics