2
$\begingroup$

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$.

$\endgroup$
10
  • 1
    $\begingroup$ 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$). $\endgroup$
    – Mabadai
    Dec 27 '21 at 10:47
  • $\begingroup$ $φ(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. $\endgroup$
    – fgrieu
    Dec 27 '21 at 10:47
  • $\begingroup$ @fgrieu Now i understand what was wrong. Is this also true that it not holds for $n$ that is multiplication of two pseudo primes? $\endgroup$
    – Mabadai
    Dec 27 '21 at 10:53
  • $\begingroup$ $φ(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$. $\endgroup$
    – fgrieu
    Dec 27 '21 at 11:06
  • $\begingroup$ @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. $\endgroup$
    – Mabadai
    Dec 27 '21 at 11:30
5
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ This definitely solves my question, and its very helpful. Thank you sir, I learned a lot. $\endgroup$
    – Mabadai
    Dec 27 '21 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.