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 = Np · Nq

GAP check

p := 433;; q := 1153;;
n := p*q;;
IsPrime(p); IsPrime(q);

2. Fermat pseudoprimes

Condition:

an−1 ≡ 1 (mod n)

Count:

Np = gcd(n−1, p−1), Nq = 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 = 2s · d (d is odd)

Compute:

ad, a2d, a4d, …, a2s·d

PASS iff:

ad ≡ 1 OR ∃ i : a2i·d ≡ −1

Otherwise: witness.

GAP check

n := 499249;;
Factors(n-1);

4. Pattern shortcut (MR counting)

If sequence pattern is:

*, *, −1, 1

Then:

a4d ≡ −1, a8d ≡ 1

Count in cyclic group of size m:

#{xk = 1} = gcd(k, m)

So:

Np = gcd(8d, p−1) − gcd(4d, p−1) Nq = gcd(8d, q−1) − gcd(4d, q−1) N = Np · Nq

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 ⇔ a4d ≡ −1, a8d ≡ 1

Split:

n = p·q, solve mod p and q

Final:

a ≡ ap (mod p), a ≡ aq (mod q)

GAP check

ChineseRem([a_p, a_q], [p, q]);

Step 1: Generator form

Let g generate (ℤ/pℤ)*:

ap = gk

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:

ap = gk

Repeat for q.

GAP check

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

Step 4: Combine

a ≡ ap (mod p), a ≡ aq (mod q)

Step 5: Second solution

If a works, then:

n − a

also works.

GAP check

PowerMod(n-a, 4*d, n);

Workflow summary