An implementation of Fermat’s algorithm that is a slight improvement on code in this book is here.

`FermatFactor[n_?OddQ]:=Module[{s=Floor@Sqrt[n+0``1],r,u,v=1}, If[s^2==n,Return@{s,s}]; {r,u}={(s+1)^2-n,2*s+3}; While[r!=0, While[r>0, r-=v;v+=2 ]; If[r<0,r+=u;u+=2] ]; (u+{-v,v-2})/2 ] `

The main improvement above is the fast implementation of Floor[Sqrt[n]] from MichaelE2. The above implementation will factor the following in less than 0.1 seconds!

`SeedRandom[100]; p=10^50; n=NextPrime@RandomInteger[{p-80000,p-60000}]*NextPrime@RandomInteger[{p+80000,p+60000}]; FermatFactor[n] (*{99999999999999999999999999999999999999999999920467,100000000000000000000000000000000000000000000075667}*) `

I have Mathematica Version 12.0.0 and FactorInteger[n] takes a very long time on that example. Can FactorInteger in Mathematica 12.2 do it in a reasonable amount of time?