I need to calculate the $d$ private key in RSA.
The data I know is $n$, $e$ and part of $q$. For calculating that d, I need to calculate $\phi = (p-1)(q-1)$, but, before I can calculate $\phi$ I need to know $q$ and $p$.
Knowing that $n = p\ \cdot q$ it should be easy to get $p$, but the problem is that $q$ isn't complete.
The solution I was thinking was to calculate the next prime number greater than $q$, then $p = \frac{n}{q}$.
The problem with that solution is that $n$ and $q$ are very large numbers and calculating the next prime number may take so long.
The values I have are:
$$q = 28715579796305758474667846518766873255492272737905466351525171318348391723088262 \\ 58249653585601622660761481080342866203785689093327148932226949505505837$$
$$n = 14634343605751036979940788054761314555865888648259143600014237897373212259787937\\988432044946495940379719810430822794442825272333645896273848057928426810706372\\6288619593719244281352195659364220185216358546968554006023167367419980981469627098 \\371458194077000595132435883250233193631515839672002808488444790391157 $$
$$e = 65537$$
My question is: How can I calculate $p$ with such a large numbers?
EDIT:
I solved my problem, maybe it's not the best solution, but it worked.
What I did was assume that the bytes from $q$ I already know must not change, so I added one new byte at the end and tried to divide $n$ by the new $q$, adding 1 to that new value if it could not divide. As the 16 possible options couldn't divide, I added one new byte and tried again.
Finally, with 4 bytes added at the end of my known $q$, I found a new one that divided $n$. After that, calculating $\phi$ was trivial.
Thanks to everyone who tried to help me.
This can be done using Coppersmith's theorem and LLL reduction (see this paper and this follow-up paper). This assumes you have about half of the bits of one of the primes.
Implementable with LLL, via Sage, e.g, like in this blog post.