# Given $φ(n)$ how can we find any combinations for $p, q$ prime numbers

Suppose i already have found that $$φ(n) = 240$$ for $$n = 900$$. How can i conclude that my $$n = pq$$ is of type $$2^2\cdot3^2\cdot5^2$$? What is $$q$$ and what is $$p$$ here?

To be more precise with my question: is it for all $$n \in \Bbb N$$ with only known $$φ(n)$$ , can i find the disassembly of $$n$$ to prime factors?

Edit(The calculation that i have done so far):

$$φ(n) = (p - 1)(q - 1)$$

$$240 = pq - (p + q) + 1$$

Substitute for $$n$$ :

$$(p + q) = 900 - 240 + 1 = 661$$

Find $$(p - q)$$:

$$(p - q)^2 = (p + q)^2 - 4pq = (661)^2 - 4\cdot900 = ... = 433,321$$ $$(p - q) = 658.271$$

From this point and on, adding $$(p - q), (p + q)$$ together obviously gives the wrong result for $$n = pq$$.

• How to find $p$ and $q$ when the given $n$ is of the "factorized prime" version. Edit: calculating p, q for $φ(900)=240$ gives decimal results for the quadratic equation, which is of course not true for $p, q$ being prime. I added my calculation to the question. I`m missing the point when $(p - q)$ gets a non even result for prime subtraction (assuming $p > q$ without loss of generality and $p, q > 2$). Dec 27 '21 at 10:47
• $φ(n)=(p - 1)(q - 1)$ does not hold for all $n=p\,q$. It holds only when $n$ is the product of two distinct primes $p$ and $q$. This is not the case for $n=900$. See e.g. this for why.
– fgrieu
Dec 27 '21 at 10:47
• @fgrieu Now i understand what was wrong. Is this also true that it not holds for $n$ that is multiplication of two pseudo primes? Dec 27 '21 at 10:53
• $φ(p\,q)=(p - 1)(q - 1)$ holds if and only if $p$ and $q$ are distinct primes; it does not in general hold for pseudoprimes. Finding $p$ and $q$ given $n=p\,q$ and $φ(n)$ by solving a quadratic equation (as you do) thus works only when $n$ is the product of two distinct primes. For something more general: first eliminate any factor of $n$ revealed by computing $\gcd(n,φ(n))$. When none is left, use that given square-free $n$ and a non-zero multiple $m$ of $λ(n)$, including $m=φ(n)$, we can factor $n$. See e.g. this, replacing $f$ with $m$.
– fgrieu
Dec 27 '21 at 11:06
• @fgrieu Im pretty lost retrieving factors of $n = 60$ using Carmichael's function. Maybe you have reference for example using numbers (and not parameters). Kindly regards. Dec 27 '21 at 11:30

We want to factor $$n=900$$ using that $$\varphi(n)=240$$, and more generally factor $$n$$ knowing the Euler totient $$\varphi(n)$$.

Leaving aside trial division, we can use three techniques

1. Taking the Greatest Common Divisor of these two givens, which if $$n$$ is divisible by a square, and some rare other cases, will reveal a factor of $$n$$, and (once the GCD itself is factored) will reveal all the factors of $$n$$, or leave a square-free $$n$$ to factor (that is $$n$$ the product of distinct primes).
2. A technique applicable to $$n$$ the product of any number of distinct primes: knowing any (non-zero) multiple $$f$$ of $$\lambda(n)$$ (the Carmichael function), including $$f=\varphi(n)$$ or $$f=e\,d-1$$ in RSA, allows factoring $$n$$ with this algorithm .
3. A simpler technique applicable to $$n$$ the product of two distinct primes $$p$$, $$q$$: we can find $$\sigma=p+q=n-\varphi(n)+1$$, then find $$p$$ and $$q$$ as the two roots of the quadratic equation $$x^2-\sigma\,x+n=0$$.

#### Using the GCD

Recall that if the factorization of $$n$$ is $$n=\prod\left({p_i}^{k_i}\right)$$ with distinct primes $$p_i$$, then $$\varphi(n)=\prod\left(\left(p_i-1\right)\,{p_i}^{k_i-1}\right)$$. Thus for all $$i$$ with $$k_i>1$$, $${p_i}^{k_i-1}$$ divides $$n$$ and $$\varphi(n)$$.

This motivates computing $$g:=\gcd(n,\varphi(n))$$. If $$g\ne1$$ (which has extremely low probability if $$n$$ is an actual RSA modulus), then $$g$$ is a non-trivial factor of $$n$$ and we have made progress: we can factor $$g$$ and $$n/g$$ separately. Further, once we have found the factorization of $$g$$, we can pull these factors from $$n$$ leaving $$n':=n/\prod\left({p_j}^{k_j}\right)$$ to factor, and with known $$\varphi(n'):=\varphi(n)/\prod\left(\left(p_j-1\right)\,{p_j}^{k_j-1}\right)$$, and now $$\gcd(n',\varphi(n'))=1$$.

If $$g=1$$, then $$n$$ is square-free (that is every $$k_i=1$$, or equivalently $$n$$ is the product of distinct primes).

Here $$\gcd(900,240)=60=2^2\cdot3\cdot5$$. Pulling these factors $$2$$, $$3$$, $$5$$ out of $$n$$, we get it's complete factorization $$900=2^2\cdot3^2\cdot5^2$$ and the problem is solved.

Thus in the following we'll move to a larger example: factor $$n=12790396087027$$, knowing $$\varphi(n)=11797951366656$$.

$$\gcd(12790396087027,11797951366656)=13$$, and that's a prime factor of $$n$$. Pulling out $$13$$ and it's powers, we have simplified the problem into factoring $$n'=n/13^2=75682817083$$ knowing $$\varphi(n')=\varphi(n)/\big(13\,(13-1)\big)=11797951366656/\big(13\cdot 12\big)=75627893376$$. Now we need the further techniques.

#### General technique for square-free $$n$$

Knowing any (non-zero) multiple $$f$$ of $$\lambda(n')$$ (the Carmichael function) helps factoring square-free $$n'$$, by using the algorithm there. We have $$f=75627893376=2^7\cdot590842917$$ thus $$s=7$$, $$t=590842917$$.

• $$a:=2$$, $$b=a^t\bmod n'=2^{590842917}\bmod 11797951366656=17605996164$$
• $$c:=b^2\bmod n'=17605996164^2\bmod 11797951366656=8570506209$$, thus $$b:=c$$.
• $$c:=b^2\bmod n'=8570506209^2\bmod 11797951366656=1$$, success!
• $$p:=\gcd(b-1,n')=\gcd(8570506209-1,11797951366656)=4327$$ which is a prime factor of $$n'$$, $$q:=n'/p=11797951366656/4327=17490829$$ which is composite, and is not a square.

We are left with factoring $$\tilde n=17490829$$ knowing $$\varphi(\tilde n)=\varphi(n')/(p-1)=17482176=\tilde\varphi$$. We could again use the general technique above, but we can also hope this time $$\tilde n$$ has only two (distinct) prime factors $$p$$ and $$q$$.

#### $$n$$ product of two distinct prime factors $$p$$ and $$q$$

We know $$p\,q=\tilde n=17490829$$ and $$(p-1)(q-1)=\tilde\varphi=17482176$$. That's a system of two equations with two unknowns. It follows $$p+q=\tilde n-\tilde\varphi+1=\sigma=8654$$, thus $$p$$ and $$q$$ are the solutions of the second degree equation $$x^2-\sigma\,x+\tilde n=0$$, thus $$p=(\sigma-\sqrt{\sigma^2-4\,\tilde n})/2=(8654-\sqrt{8654^2-4\cdot17490829})/2=3217$$ and $$q=(\sigma+\sqrt{\sigma^2-4\,\tilde n})/2=(8654+\sqrt{8654^2-4\cdot17490829})/2=5437$$. Both $$p$$ and $$q$$ are prime, thus our hopes were founded, and in the end the desired factorization is $$n=12790396087027=13^2\cdot3217\cdot4327\cdot5437$$.

• This definitely solves my question, and its very helpful. Thank you sir, I learned a lot. Dec 27 '21 at 13:03