# Exercise 3 Cheat Sheet -- RSA

---

## Recognition

- **(a)** Given p, q, e, c → RSA decryption.
- **(b)** Given n, e, d → Factor n using ed-1.
- **(c)** Count bases causing the factorization algorithm to stop at a given step.

---

## Key Formulas

    n = p*q,       φ(n) = (p-1)(q-1)

    e*d ≡ 1 (mod φ(n))

    m ≡ c^d (mod n)

    k = ed - 1 = 2^s * t,    t is odd

    ┌───────────────────────────────────────────────────┐
    │  ed - 1  is a multiple of φ(n)                   │
    └───────────────────────────────────────────────────┘

---

## A. RSA Decryption

    φ = (p-1)(q-1)
    d = e^(-1) mod φ
    m ≡ c^d (mod n)

**GAP**
```
phi := (p-1)*(q-1);
InverseMod(e, phi);
PowerMod(c, d, n);
```

---

## B. Factoring n from d

1. Compute

       k = ed - 1 = 2^s * t

2. Compute

       x ≡ a^t (mod n)

   If x = ±1, the base fails.

3. Repeat

       y ≡ x^2 (mod n)

   If y ≠ 1, set x ← y.

   Stop when

       y = 1  and  x ≠ ±1

4. Recover

       ┌───────────────────────────────────────────────────┐
       │  p = gcd(x-1, n),    q = gcd(x+1, n)             │
       └───────────────────────────────────────────────────┘

   Verify p*q = n.

**GAP**
```
PowerMod(a, t, n);
PowerMod(x, 2, n);
Gcd(x-1, n);
Gcd(x+1, n);
FactorsInt(n);
```

---

## C. Count Bases Found at Step t

Let

    k = 2^s * m

and define

    E = 2^t * m

Suppose the desired factor is p and the other prime is q.

Modulo p:

    x^(2E) ≡ 1,    x^E ≢ 1

    ┌───────────────────────────────────────────────────────┐
    │  N_p = gcd(2E, p-1) - gcd(E, p-1)                    │
    └───────────────────────────────────────────────────────┘

Modulo q:

    x^(2E) ≢ 1

    ┌───────────────────────────────────────────────────────┐
    │  N_q = (q-1) - gcd(2E, q-1)                          │
    └───────────────────────────────────────────────────────┘

By CRT:

    ┌───────────────────────────────────────────────────────┐
    │  N = N_p * N_q                                       │
    └───────────────────────────────────────────────────────┘

Useful fact:

    ┌───────────────────────────────────────────────────────┐
    │  #{x : x^r ≡ 1 (mod p)} = gcd(r, p-1)               │
    └───────────────────────────────────────────────────────┘

**GAP**
```
Gcd(2*E, p-1);
Gcd(E, p-1);
Gcd(2*E, q-1);
ChineseRem([a,b], [p,q]);
```

---

## Remember

- ed-1 ≠ φ(n) in general.
- t must be odd.
- If a^t = ±1, choose another base.
- Stop at the *first* occurrence of y = 1.
- Always verify p*q = n.