# RSA find $q$ given only $e$ and $p$

Lets say hypothetically all one knew was a value of $$e$$ and a value of $$p$$.

As an example, lets assume that $$e = 13$$ and $$p = 67$$.

Would it be possible to find the value of $$q$$ from this equation?

$$\gcd(13, (66)(q-1)) = 1$$

If so, how would I begin solving this?

• Note that this is equivalent to $\gcd(13,q-1)=1$ in terms of constraints (not in value!) – SEJPM Dec 4 '18 at 20:36
• is this a homework or CTF? – kelalaka Dec 4 '18 at 20:43
• Might you actually intend to ask "how do I find $d$ such that $e \cdot d = 1 \pmod p$"? – poncho Dec 4 '18 at 21:06
• Well obviously you need $n$. – forest Dec 5 '18 at 2:27
• Possible duplicate of RSA limiting down the possible values for $n,q$, and $d$? given only $e$ and $p$ – forest Dec 5 '18 at 9:08

Do you mean $$n$$ is unknown? Then there are infinitely many $$q$$ which will work. Since 13 and 66 are relatively prime, by @SEJPM's comment, all $$q$$ which are of the form $$q_k \neq 13k+1,$$ are possible solutions. Depending on what $$n$$ you want you can take $$k$$ large enough. But in the RSA context $$n$$ must be public.