# Factors calculation in RSA

You are given $$d\bmod(p-1)$$ , $$d\bmod(q-1)$$ , $$\operatorname{invert}(p,q)$$ and $$p\bmod2^{200}$$, the public exponent is $$e=65537$$.

$$\operatorname{invert}(p,q)$$ is the answer of $$p*x \equiv 1 (mod\quad q)$$

$$d$$ is the private exponent, the modulus is unknown.

Is there some way to calculate $$p$$, $$q$$?

• The added information tells that $\operatorname{invert}(p,q)$ designates $p^{-1}\bmod q$. That's not $q_\text{inv}=q^{-1}\bmod p$ usually part of an RSA private key.
– fgrieu
Jul 11, 2021 at 8:03
• @fgrieu: actually, it is usually a part of the RSA private key (swap which prime is called $p$ and which is called $q$) Jul 11, 2021 at 11:17
• @Manc You may want to consider voting up the answer that you accepted. Jul 11, 2021 at 12:31

You are given $$d \bmod(p−1)$$.., the public exponent is $$e=65537$$. Is there some way to calculate $$p$$?

Well, we know that $$d_p = d \bmod p-1$$ and $$e$$ are related by $$d_p \cdot e = 1 + kp$$, for some integer $$k$$, and that $$k < 65537$$

So, do a partial factorization of $$d_p \cdot e - 1$$ into $$a \cdot b$$, where $$a$$ consists of factors below 65537 and $$b$$ has no such factors (which is quite easy). We know that $$p = (a/c) b$$, where $$c$$ is a factor of $$a$$; $$a$$ is relatively small, and so there are only a few such factors to consider. And because we know

$$p \bmod 2^{200}$$

It's easy to distinguish which one it is.

And, for the other half of the question:

Is there some what to calculate $$q$$

We can use the same trick, except using the known $$p^{-1} \bmod q$$ value as the distinguisher...

• Thanks a lot for your help!!❤
– Manc
Jul 11, 2021 at 11:54