# Use Fermat-Kraitchik’s factorization to factor $85026567$

factoringprime factorization

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?

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