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$!