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
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
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.RSA Primes from Modulus and Totient explained
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: , so . 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 . The discriminant is , whose square root is 8, and the roots are : 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 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
- = Modulus
- = Totient
- = Larger prime
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