RSA Primes from Modulus and Totient

Also known as recover p and q · factor rsa from phi · break rsa with totient · p q from n phi

p=S+S2−4n2,S=n−φ+1p = \frac{S + \sqrt{S^2 - 4n}}{2}, \quad S = n - \varphi + 1

Units aren’t used in this calculation: every value is a plain number.

sig figs

Worked example: n = 3233 and φ = 3120 → the larger prime is 61. Press Try an example to run it live, then adjust anything.

Enter your known values, leave one input blank, and solves for the missing one. Tap a variable’s symbol to see what it means, with a typical value.

Where RSA Primes from Modulus and Totient fits

Missing an input?

See also

RSA Modulus: Multiply the recovered primes back to check they give n.RSA Totient: Where the φ this needs comes from.Totient of a Prime Power: Both use euler totient and larger prime.
Learning zone

RSA Primes from Modulus and Totient explained

nφpq

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: φ=(p−1)(q−1)=pq−p−q+1\varphi = (p-1)(q-1) = pq - p - q + 1, so p+q=n−φ+1p + 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=1143233 - 3120 + 1 = 114. The discriminant is 1142−4⋅3233=12996−12932=64114^2 - 4 \cdot 3233 = 12996 - 12932 = 64, whose square root is 8, and the roots are (114±8)/2(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 S2−4nS^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.

RSA Primes from Modulus and Totient formula

p=S+S2−4n2,S=n−φ+1p = \frac{S + \sqrt{S^2 - 4n}}{2}, \quad S = n - \varphi + 1
Where
  • nn= Modulus
  • φ\varphi= Totient
  • pp= Larger prime
Revised 1 November 2026
Cite this page

formula.expert. (2026, November 1). RSA Primes from Modulus and Totient Formula & Calculator. https://formula.expert/solvers/rsa-primes-from-modulus-and-totient