Re: [OT] On factoring integers of the form n=(x^D+1)(y^D+1) and n=(x^D+a_(D-2)x^(D-2)+...a_{D-2}(x^{D-2}))(y^D+b_{D-2}(y^{D-2}+...b_0)) with x,y of the same size

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Sep 27, 2025 at 04:07:36PM +0300, Georgi Guninski wrote:
> Apologies for OT.
> 
> >From our preprint [1].
> 
> > We got plausible algorithm and strong numerical evidence
> that integers of the form $n=(x^D+a_{D-2}x^{D-2}+\cdots a_0)
> (y^D+b_{D-2}y^{D-2}+\cdots b_0)$ with $x,y$ of the same size
> and $C=\max\{a_i,b_i\}$ and $a_i \ge 0,b_i \ge 0$ can be factored in
> $O(\mathrm{polynomial}(C \log(n)))$. A special case for $D>1$ is
> $n=(x^D+1)(y^D+1)$ We tested thousands of testcases without failure.

Well, this does not work for f=x^D, g=y^D.

But let me guess, you are computing r~n^(1/D) and solve
the system:

x*y = r
f(x)*g(y) = n

n=(x*y)^D + a_{D-2}*x^{D-2}*y^D + b_{D-2}*x^D*y^(D-2) + ...
n=(x*y)^D * ( 1 + a_{D-2}/x^2 + b_{D-2}/y^2 + ...

so
n^(1/D) = (x*y) * (1+(a_{D-2}/x^2 + b_{D-2}/y^2)/D +...)
n^(1/D) - (x*y) = a_{D-2}*y/x/D + b_{D-2}*x/y/D +...

so as long as x/y~1 and C small this should work but I do not expect your
algorithm to work if x ~ sqrt(y), for example 
x= nextprime(2^128); y= nextprime(2^256);

Cheers,
Bill.