RSA Algorithm
[1] Let P, Q be primes[2] Then Φ(PQ) = (P-1)(Q-1)
[3] Euler's Totient Theorem states: aΦ(n) ≡ 1 (mod n) for a, n coprime
[4] Substituting [2] into [3]: aΦ(PQ) ≡ 1 (mod PQ) for a, PQ coprime
[5] And aS*Φ(PQ)+1 ≡ a (mod PQ) for any integer S (properties of modular exponentiation)
[6] Choose encryption key, E, such that E is coprime to Φ(PQ)
[7] Derive decryption key, D, the modular inverse of E: D*E ≡ 1 mod Φ(PQ)
[8] D*E = S*Φ(PQ) + 1 for some S
[9] Substituting [8] into [5]: aD*E ≡ a (mod PQ)
[10] Discard P, Q
[11] Publish E, PQ as public key
[12] Retain D as private key
[13] To encode message m:
c = mE (mod PQ)
m = cD (mod PQ) = mD*E (mod PQ) = m
Miller-Rabin Primality Test
Let p be an odd prime.For any x where x2 ≡ 1 (mod p):
[1] (x2 - 1) ≡ 0 (mod p)
[2] (x + 1) · (x - 1) ≡ ±0 (mod p)
[3] x ≡ ±1 (mod p) Fermat's Little Theorem states:
[4] xp-1 ≡ 1 (mod p) for p prime. Represent p by 2k· m - 1 where m is odd
[5] Then p-1 = 2k· m Choose any a where 1 ≤ a ≤ p.
Substituting [5] into [4]:
[6] a2k· m ≡ 1 (mod p)
[7] a2k· m = a2*(2k-1·m) = [a(2k-1· m)]2 ≡ 1 (mod p)
From [3]:
[8] a2k-1m ≡ ±1 (mod p)
If a2k-1m ≢ -1 (mod p) then a2k-1m ≡ +1 (mod p)
Repeating [6] through [8], replacing: 2k with 2k-1:
If a2k-2m ≢ -1 (mod p) then a2k-2m ≡ +1 (mod p) Proceeding by induction, if each of a2km, a2k-1m, a2k-2m, ... a2m ≢ -1 (mod p) then am ≡ ±1 (mod p) Therefore, either:
[i] am ≡ 1 (mod p) or [ii] one of am, a2m, ... , a2k-1m ≡ -1 (mod p) To test if a given odd number, n is prime: [A] Represent n-1 as 2k · m
[B] Choose a1 such that 1 < a1 < n
[C] Calculate a20m, a21m, ... , a2k-1m (mod n) for 0 ... k-1.
[D] If neither [i] or [ii] is true for any 0 ... k-1, then n is composite. a is a witness
[E] If either [i] or [ii] is true, this is a necessary (but not sufficient) condition for n being prime.
[F] Repeat [B] through [E] for independent a, a2 through aj
The probability that n is prime is given by 1 - (0.25)j, where j is the count of a that have been tested.