I have to use Fermat-Kraitchik’s factorization to factor $n=85026567$. I already know that $85026567$ is divisible by $3$, and therefore $85026567=3\cdot 28342189$, and both of the factors are prime. However I am interested in the method rather than the result, so I will proceed as if I didn't know this factorization.
I know that $\sqrt{n}\approx 9220.985$. Let $Q(x)=x^2-n$ and $t_i=\lfloor\sqrt{n}\rfloor+i$. Therefore:
\begin{align*}
t_1=9221 \quad& Q(t_1)=274=2\cdot 137 \\
t_2=9222 \quad& Q(t_2)=18717=3\cdot 17 \cdot 367\\
t_3=9223 \quad& Q(t_3)=37162=2\cdot17\cdot 1093\\
\vdots \quad& \quad \quad\quad\quad\quad\quad\quad \vdots
\end{align*}
I have done a few more but I always get one big prime in the factorization of $Q(t_i)$ and therefore I cannot proceed. I have tried doing $t_i=\lfloor\sqrt{kn}\rfloor+i$ for $k=2,3,4,5$ (and therefore $Q(x)=x^2-kn$) but I still get no results. I don't know what to do. Could someone help me?
Best Answer
This method works quickly when the factors are close together. In this case, the factors are very far apart, so the associated $t_i$ will be huge.
Remember why this method works: $x^2-n=y^2$ means $n=x^2-y^2=(x-y)(x+y)$. In this example, we want to "discover" this factorization when $x-y=3$ and $x+y=28342189$, which means that $x=14171096$ and $y=14171093$. So this method won't find the factorization until $t_i=14171096$!