Constructing an integer with specific totient without factorization

Question

Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without factoring $N$?

Answer 1

Remark: $p$ and $q$ are distinct odd primes (if not, we can factor $N$), thus $\phi(N)=(p-1)(q-1)$. Define $p'=(p-1)/2$ and $q'=(q-1)/2$. It holds $\phi(N)=4\,p'\,q'$.

What's asked is not always possible. As a counterexample, assume $k=2$ (which is a possible $k$, from above remark), and $p\equiv 3\equiv q\pmod4$ (which covers about 25% of RSA keys). If we could find $N^*$ with $\phi(N^{*})=\phi(N)/k$, it would hold $\phi(N^*)=2\,p'\,q'$ with $p'$ and $q'$ odd. Therefore¹ $N^*$ would be of the form $2^s\,r^t$ with $r$ prime, with $\phi(N^*)=(r-1)\,r^{t-1}$. Therefore we could factor $N^*$, yielding $r$ and $e$, thus $\phi(N^*)$, thus $\phi(N)$, allowing to factor $N$.

Still with $k=2$, $p\equiv3\pmod4$, but this time $q\equiv5\pmod8$ (which covers another about 25% of RSA keys), we have $\phi(N^*)=4\,p'\,q''$ with $p'$ and $q''=(q-1)/4$ odd, and the two possible (non-exclusive) options are²

• that $N^*$ is of the form $2^s\,r^e$ with $r$ prime, which we handle as above.
• that $N^*=(2\,p'+1)\,(2\,q''+1)$ with $(2\,p'+1)$ and $(2\,q''+1)$ distinct primes, in which case $N^*=p\,((q+1)/2)$, thus $\gcd(N,N^*)$ will be $p$, yielding a factorization of $N$.

More generally, if what is asked was possible, there is some chance that at least one of the following holds:

• $\gcd(N,N^*)$ reveals a factor of $N$.
• we can factor $N^*$ (including but not limited to $N^*=2^s\,r^t$), then can compute $\phi(N^*)$, thus $\phi(N)$, allowing us to factor $N$.

I have a feeling that's a fair chance for random $N$ when $k$ is small.

Independently: When $k$ is large, and especially when it is prime, it's value is revealing: it must divide $p-1$ or $q-1$, thus $\gcd(N,j\,k+1)$ will be $p$ or $q$ for some $j$, and it is worth trying to find $j$ by enumeration at least when $\sqrt N/k$ is small enough and there is no reason to believe that $\max(p,q)/\min(p,q)$ is large.

When $k$ has a large prime factor $k'$ that we can find, that $k'$ must divide $p-1$ or $q-1$, and we may be able to use the same approach to factor $N$. And with a bit of luck, the product $k'\,k''$ where $k''$ is a large factor of $k/k'$ will divide $p-1$ or $q-1$, allowing to factor $N$. And even if we can't fully factor $k$, because the largest factor we find is composite, it still has a fair chance to divide $p-1$ or $q-1$, allowing to factor $N$.

---

I vaguely conjecture (would not bet the house) that there are vanishingly few semiprimes $N$ such that an oracle knowing its factorization could reveal $k$, $N^*$ as in the question without the combination of the above techniques being of great help to factor $N$. In other words, what's asked would demonstrably be impossible for overwhelmingly most $N$.

---

¹ This uses the following lemma: if $\phi(m)\equiv2\pmod4$, then $m$ is of the form $2^s\,r^t$ with $r$ prime. Proof of that lemma can be by contraposition using the expression of Euler's totient: $$\phi\left(\prod_{p_i\text{ distinct primes}} {p_i}^{e_i}\right)=\prod_{\text{same }(p_i,e_i)}(p_i-1)\,{p_i}^{(e_i-1)}$$

² This is left as an exercise to the reader, using the same kind of argument as for the above lemma.