Key Formulas
n = p·q, φ(n) = (p−1)(q−1)
e·d ≡ 1 (mod φ(n))
m ≡ cd (mod n)
k = ed − 1 = 2s · t, t is odd
ed − 1 is a multiple of φ(n)
A. RSA Decryption
φ = (p−1)(q−1)
d = e−1 mod φ
m ≡ cd (mod n)
GAP
phi := (p-1)*(q-1);
InverseMod(e, phi);
PowerMod(c, d, n);
B. Factoring n from d
- Compute
k = ed − 1 = 2s · t
- Compute
x ≡ at (mod n)
If x = ±1, the base fails.
- Repeat
y ≡ x2 (mod n)
If y ≠ 1, set x ← y. Stop when
y = 1 and x ≠ ±1
- 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 = 2s · m
and define
E = 2t · m
Suppose the desired factor is p and the other prime is q.
Modulo p:
x2E ≡ 1, xE ≢ 1
Np = gcd(2E, p−1) − gcd(E, p−1)
Modulo q:
x2E ≢ 1
Nq = (q−1) − gcd(2E, q−1)
By CRT:
N = Np · Nq
Useful fact:
#{x : xr ≡ 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]);