Finding p and q in RSA with a given n, |p-q|<10000 I've got an RSA encryption I need to crack, but to do it I need to find the p and q values of an N I am given - it's quite large, around 308 symbols.
I know that N is the product of primes p &amp; q, but I don't know what kind of searching algorithm I'd implement to find the exact p &amp; q that fit |p-q|&lt;10000. Since it needs to be an efficient method, I'm looking for a way that excludes finding ALL possible combinations of p*q = n.
How would I go about doing it? How would I even start with inputting the 308 symbol number anywhere? It's too large to fit any kind of variable in c# for example...
As @fgrieu said, it will work when ${|p-q|&lt; N^{1/4}}$ , where ${\sqrt N}$ and ${A}$ both are very nearer. then we can take ${A = \sqrt N}$ to start with.

Let ${A=(p+q)/2}$ , i.e., A is mid point of p and q, which could be nearer to ${\sqrt N}$

There exist an integer ${x}$ so that, ${A-x=p}$ and ${A+x=q}$

${N=pq}$ ${=}$ ${(A-x)(A+x)=A^2-x^2}$

${x= \sqrt{A^2-N}}$

Since we know A and N we can find x and subsequently p and q.