Question: p and q are safe primes and with 1000 digits. Argue for or against if its easy on a Laptop to solve RSA-problem using Fermat's factorization method.
Answer:
First note that when p and q are approximately of the same size, the have the most secure scenario. Using Fermat's method: Find $(⌊\sqrt{N}⌋+i)^2-N=j^2$ for $i=1,2,3,...$. Then we check if gcd$(i-j,N)$ nontrivial. If $p=2a+1$ and $q=2b+1$, if a and b are primes, we get for some i that gives us a square j: gcd$(i-\sqrt{(⌊\sqrt{(2a+1)(2b+1)}⌋+i)^2-(2a+1)(2b+1)},(2a+1)(2b+1))$
What can I get from this?