I'm looking at the following problem. I know the basic algorithm, but to be honest, I'm kind of lost on how to solve part (a). I think I've solved (b) and (c) based on what the problem says and my class notes, and I'm hoping (d) and (e) will make more sense once I solve (a).
Let $p$ and $q$ be odd primes with difference $\delta=p-q>0$ and product $n=pq$.
(a) Show that the Fermat factorization method involves $(p+q)/2 - \lceil\sqrt{n}\rceil$ increases in $x$ to find $x$ and $y$ such that $n=x^2-y^2$.
(b) Show that $$\bigg({{p+q}\over{2}} - \sqrt{pq}\bigg)\bigg({{p+q}\over2} + \sqrt{pq}\bigg)={1\over4}\delta^2 $$ (c) Assume that $\delta$ is so much smaller than $p$ that we can consider $(p+q)/2 \approx p$ and $√(pq) ≈ p$. Show that then $$\bigg({{p+q}\over{2}} - \sqrt{pq}\bigg)\approx\delta^2/(8p)$$ (d) Suppose that $p$ and $q$ are 100-digit primes (so that $p, q \approx 10^{99}$) and $p − q \approx 10^{80}$ so the most significant $19$ or $20$ digits are the same. Show that the Fermat algorithm takes approximately $10^{60}$ increases in $x$.
(e) If $p$ and $q$ are $100$-digit primes with $p − q \approx 10^{50}$, show that the Fermat method finds the factorization with very few increases in $x$.
So for part (a), I know the algorithm says we start at $x = \lceil\sqrt{pq}\rceil$ and increase $x$ until we get a $y^2$ such that $y^2 = x^2- n$, meaning that $x^2 - n$ is a square.
That can obviously be rearranged to $n=x^2-y^2$ which is what the problem says. I'm just not sure how to find that that's the number of increases in $x$ it will take.
Assume that $n$ is not a square and define $u:=trunc(\sqrt{n})$
Start with $x=u$ and increase $x$ until $x^2-n$ is a square. Then, the number of increases is $x-u$