# Crypto Exam Formula Card
## Fermat + Miller--Rabin + CRT (with GAP)

---

## 1. Setup (always first)

Let:

    n = p * q     (p, q primes)

Split everything:

    x mod n  ↔  (x mod p,  x mod q)

Final count always:

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

### GAP check
```
p := 433;; q := 1153;;
n := p*q;;
IsPrime(p); IsPrime(q);
```

---

## 2. Fermat pseudoprimes

Condition:

    a^(n-1) ≡ 1 (mod n)

Count:

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

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

### GAP check
```
Gcd(n-1, p-1);
Gcd(n-1, q-1);
```

---

## 3. Miller--Rabin (only rule you need)

Write:

    n-1 = 2^s * d     (d is odd)

Compute:

    a^d,  a^(2d),  a^(4d),  ...,  a^(2^s * d)

**PASS iff:**

    ┌─────────────────────────────────────────────────────┐
    │  a^d ≡ 1   OR   ∃ i : a^(2^i * d) ≡ -1            │
    └─────────────────────────────────────────────────────┘

Otherwise: witness.

### GAP check
```
n := 499249;;
Factors(n-1);
```

---

## 4. Pattern shortcut (MR counting)

If sequence pattern is:

    *,  *,  -1,  1

Then:

    a^(4d) ≡ -1,    a^(8d) ≡ 1

Count in cyclic group of size m:

    ┌──────────────────────────────────────────┐
    │  #{x^k = 1} = gcd(k, m)                 │
    └──────────────────────────────────────────┘

So:

    ┌─────────────────────────────────────────────────────┐
    │  N_p = gcd(8d, p-1) - gcd(4d, p-1)                │
    └─────────────────────────────────────────────────────┘

    ┌─────────────────────────────────────────────────────┐
    │  N_q = gcd(8d, q-1) - gcd(4d, q-1)                │
    └─────────────────────────────────────────────────────┘

Final:

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

### GAP check
```
Gcd(8*d, p-1) - Gcd(4*d, p-1);
Gcd(8*d, q-1) - Gcd(4*d, q-1);
```

---

## 5. Miller--Rabin Construction (*, *, -1, 1)

Goal:

    *,  *,  -1,  1  ⇔  a^(4d) ≡ -1,  a^(8d) ≡ 1

Split:

    n = p*q,    solve mod p and q

Final:

    a ≡ a_p (mod p),    a ≡ a_q (mod q)

### GAP check
```
ChineseRem([a_p, a_q], [p, q]);
```

---

### Step 1: Generator form

Let g generate (Z/pZ)*:

    a_p = g^k

### GAP check
```
g := PrimitiveRootMod(p);
```

---

### Step 2: Fix target value

    g^ℓ ≡ -1 (mod p)  ⇒  ℓ = (p-1)/2

### GAP check
```
PowerMod(g, (p-1)/2, p);    # should give -1 mod p
```

---

### Step 3: Exponent equation

    4d * k ≡ ℓ (mod p-1)

Solve:

    k ≡ (4d)^(-1) * ℓ (mod p-1)

Then:

    a_p = g^k

Repeat for q.

### GAP check
```
k := (4*d)^-1 * ((p-1)/2) mod (p-1);
PowerMod(g, k, p);
```

---

### Step 4: Combine

    a ≡ a_p (mod p),    a ≡ a_q (mod q)

---

### Step 5: Second solution

If a works, then:

    n - a

also works.

### GAP check
```
PowerMod(n-a, 4*d, n);
```

---

### Workflow summary

- Write a = g^k
- Replace -1 by (p-1)/2
- Solve 4dk ≡ (p-1)/2
- Build a_p, a_q
- CRT