RSA Primes from Modulus and Totient

This is the demonstration that φ(n) is not a harmless extra number. Knowing n and φ together, you get p and q with no factoring at all. The trick is that you already have their sum and their product. The product is n. The sum falls out of the totient: $\varphi = (p-1)(q-1) = pq - p - q + 1$, so $p + q = n - \varphi + 1$. Two numbers with a known sum and product are the two roots of a quadratic, and the quadratic formula finishes it in one line.

Work the textbook key through. n = 3233, φ = 3120, so the sum is $3233 - 3120 + 1 = 114$. The discriminant is $114^2 - 4 \cdot 3233 = 12996 - 12932 = 64$, whose square root is 8, and the roots are $(114 \pm 8)/2$ — 61 and 53. This page returns the larger one; subtract from the sum, or divide n by it, to get the other.

The security lesson is that φ must be protected exactly as carefully as p and q, and it is why a key's parameters are never partially disclosed. It also gives you a free consistency test: if a claimed n and φ do not belong to the same key, the discriminant $S^2 - 4n$ comes out negative and there are no real roots at all, which the solver will tell you rather than returning nonsense. A positive discriminant that is not a perfect square is a subtler mismatch — the roots exist but are irrational, so they are not primes and the pair is still wrong.