# 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 & q, but I don't know what kind of searching algorithm I'd implement to find the exact p & q that fit |p-q|<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...

• Fermat factorization? – kelalaka Jan 8 at 19:41
• Or just brute force searching around $\sqrt{N}$ – poncho Jan 8 at 19:43
• docs.microsoft.com/en-us/dotnet/api/… – kelalaka Jan 8 at 20:00
• For RSA numbers of cryptographic size, simplified Fermat will do: compute $a=\left\lceil\sqrt N\right\rceil$, $p=a+\sqrt{a^2-N}$ which will always be an integer, and $q=a-\sqrt{a^2-N}$. – fgrieu Jan 8 at 20:42
• I presume symbols means decimal digits? – kodlu Jan 8 at 23:55

As @fgrieu said, it will work when $${|p-q|< 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}}$$