Engineering / Mathematics — Primality Testing
Factoring and Computing Euler's Phi Function
The polynomial-time equivalence between factoring a modulus, computing phi, and recovering an RSA private exponent.
Executive summary
Three problems that appear distinct are polynomial-time equivalent for RSA moduli: factoring n, computing phi(n), and recovering the private exponent d from the public key.
This equivalence is what gives RSA a single mathematical foundation rather than several independent ones.
Learning objectives
- Prove that phi(n) yields the factorisation for a semiprime.
- Sketch the reduction from d to the factorisation.
- State what the equivalence does and does not establish.
01Phi yields the factorisation
Phi to factors
For n = pq with distinct primes, knowledge of φ(n) gives p and q in polynomial time.
Proof. φ(n) = (p−1)(q−1) = n − (p+q) + 1, so p + q = n − φ(n) + 1. With the sum S and product n known, p and q are the roots of x² − Sx + n = 0, obtained by an integer square root.
The converse direction is immediate: the factorisation gives φ(n) by the product formula. So the two problems are equivalent for semiprimes.
p, q = (S ± √(S² − 4n)) / 2, S = n − φ(n) + 102The private exponent yields the factorisation
Recovering the factorisation from d is less immediate but also polynomial time, using a randomised procedure resembling Miller–Rabin.
Form ed − 1
This is a multiple of λ(n), hence a multiple of the group exponent.
Write it as 2^s · t with t odd
Separating the powers of two, as in Miller-Rabin.
Pick a random base and square repeatedly
Compute a^t, then square, watching for a non-trivial square root of 1.
Extract a factor
A non-trivial square root x of 1 gives gcd(x − 1, n) as a proper factor.
The procedure succeeds with probability at least one half per random base, so a handful of attempts suffices. The mechanism is the same structural fact Miller–Rabin exploits: a composite modulus has more than two square roots of unity.
03What the equivalence establishes
| Problem | Reduces to | Direction |
|---|---|---|
| Factor n | Compute φ(n) | Both ways |
| Factor n | Recover d | Both ways |
| Break RSA encryption | Factor n | One way only — not known to be equivalent |
So RSA's security rests on the RSA assumption, which is implied by but not known to imply the hardness of factoring. In practice the best known attack on the RSA problem is to factor, which is why the distinction is theoretical rather than operational.
04Frequently asked questions
Does this mean φ(n) must be kept secret?
Yes, as secret as the factorisation itself, because they are equivalent. Any protocol revealing φ(n) reveals the private key.
Is breaking RSA equivalent to factoring?
Not known. There is evidence suggesting the two may not be equivalent for small public exponents, but no attack exploiting the gap is known. In practice the assumption is treated as sound.
Why does recovering d need randomisation?
Because the extraction relies on finding a base whose squaring sequence exposes a non-trivial square root of unity, and not every base does. Random choice succeeds with constant probability per attempt.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 262-267.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.