[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

[Georgi Guninski <gguninski@gmail.com>]

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.

The preprint define $r_1=\lfloor n^{\frac1D}\rfloor-x_0 y_0$
and conjectures that $r_1$ is "small".

Given $n=f(x_0)g(y_0),f(x),g(y)$, assume we are given $r_1$ too.
Then we can find $x_0,y_0$ as the integer solutions of

$$ [f(x)g(y)-n,x y-(\lfloor n^{\frac1D}\rfloor-r_1)]$$
with complexity of finding the integer root of univariate polynomial.

This corresponds to the factors of $n$ which are $f(x_0),g(y_0)$.

We don't know $r_1$, but by the conjecture it is in a short known
interval and we enumerate all possibilities.



Example session:

```
Kx.<x,y>=QQ[]
B=2**400;f1=x^4+5*x^2+1;f2=y^4+14*y^2+2;x0,y0=[randint(B,2*B) for _ in
(1,2)];n=f1(x0,0)*f2(0,y0)
%time ss=guninski_fg(n,f1,f2,L=None,allsols=False,prot=1) #Wall time: 71.5 ms
print("log(sol,2)=",RR(ss[0]).log(2)) #log(sol,2)= 1602.01840756461
```

1. Is this correct?
2. Is this known?
3. Can it be improved?

[1] https://www.researchgate.net/publication/395877507_On_factoring_integers_of_the_form_n_x_D_1y_D_1_and_n_x_D_a_D-2_x_D-2_a_0_y_D_b_D-2_y_D-2_b_0_with_x_y_of_the_same_size

Attached is sage code, with link which can be run in a browser.

"""

sage code for the paper: 

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

https://www.researchgate.net/publication/395877507_On_factoring_integers_of_the_form_n_x_D_1y_D_1_and_n_x_D_a_D-2_x_D-2_a_0_y_D_b_D-2_y_D-2_b_0_with_x_y_of_the_same_size



"""

def guninski_fg(n,f,g,L=None,prot=False,allsols=False):
	"""
	n: integer to be factor, L:  bound

	f=x^D+O(x^(D-2)),g=y^D+O(y^D-1), x ~ y <=> floor(log(x_0))=floor(log(y_0))
	n=f(x_0)*g(y_0)

	C is maximum coefficient of f,g and it must be small for efficiency

	the coefficient a_i of f and b_i of g must be nonnegative

	complexity including failure:  O(C log_2(n)  univariate polynomial factorizations over the integres)
	returns list of factors of n or empty on failure

	usage:

	Kx.<x,y>=QQ[]
	
	B=2**400;f1=x^4+5*x^2+1;f2=y^4+14*y^2+2;x0,y0=[randint(B,2*B) for _ in (1,2)];n=f1(x0,0)*f2(0,y0)
	%time ss=guninski_fg(n,f1,f2,L=None,allsols=False,prot=1)
	print("log(sol,2)=",RR(ss[0]).log(2))

	author:  Georgi Guninski Wed Sep 24 02:55:02 PM UTC 2025
	"""
	sols=[]
	X,Y=f.parent().gens()
	KX=QQ[str(X)]
	D=f.degree()
	assert D==g.degree(),"g.degree() != f.degree()"
	assert f.coefficient({X:D-1})==0,"X^(D-1) != 0"
	assert g.coefficient({Y:D-1})==0,"Y^(D-1) != 0"
	C=max([i for i,j in f])
	C=max([C]+[i for i,j in g])
	if L is None:  L=floor(C*log(n,2))
	if prot:  print("L=",L," log_2(L)",floor(log(L,2)))
	F=f*g-n
	t=floor(AA(n)**(1/QQ(D)))
	for r_0 in range(L):
		Y1=(t-r_0)/X
		F2=F.subs({Y:Y1})
		F2=KX(numerator(F2))
		ro=F2.roots(multiplicities=False)
		ro=[ZZ(i) for i in ro if denominator(i)==1]
		sol=[gcd(f(i,0),n)%n for i in ro if gcd(f(i,0),n)%n>1]
		if not sol:  continue
		if prot:  print("Solution at ro=",r_0,"log_2(g)=",[floor(RR(i).log(2)) for i in sol])
		sols += sol
		sols=list(set(sorted(sols)))
		if not allsols:  break
	return sols

def getpolydm2(D,C,X,D2=2):
	# for guninski_factor_fg
	return X**D+sum(X**i * randint(0,C) for i in range(D-D2+1))

def benchmark_fg(lim,D=3,BC=10,B=2**200,D2=2):
	bad=0
	badss=0
	Kx.<x,y>=QQ[]
	i0=0
	badl=[]
	while i0 < lim:
		f1=getpolydm2(D,BC,x,D2=D2)
		f2=getpolydm2(D,BC,y,D2=D2)
		x0=randint(B,4*B)
		y0=randint(B,4*B)
		#print(f1,f2)
		p1=f1(x0,y0)
		p2=f2(x0,y0)
		#if gcd(p1,p2) != 1:  continue
		i0 += 1
		n=p1*p2
		ss=guninski_fg(n,f1,f2,L=None,allsols=False,prot=True)
		goo=any([gcd(i,n)%n for i in ss if gcd(n,i)%n>1])
		
		if not goo:  
			bad += 1
			badl += [(n,D,f1,f2,x0,y0)]
		if not ss:  badss += 1
		print(i0,'bad=',bad,badss,goo)
		
	return bad,badl

#You can the code in a browser at:
# https://sagecell.sagemath.org/?z=eJy9VlFv2zYQfk6A_AfOSVHKZhxJTdDNKQs0NtKHesvSdphTIxVkm1LYSqQgUo3Vovvtu6MkOzH6sGHAEIcWeXfk8bvvPrnX6x3sH-yP9UqQRJfE3glSxIUoRwTXrxRJ4qXVpVQpkcqKVJSG6MT5gX9OjhSn64-TQeDR2n0dkVitNstx9G1yHH5ff3RfgwGJI98jznXRmOrWRBZgOSL30t6RozWrj7pjTJzDIL8KTOjO2sKMTk7u7--HpTAiLpd3aWzFUAl7UlSLTC5jK7U6efbL2c_Pn5_5z6MrFW3uEHV3iHQSweYR3iFS0TqaREGNQwTZtwtxBInhE4yQdoT2hZvVboSEI0wXXOpuP0w26pLFv14D8EokJK2UVOazjJKUKpawlE35b1oJVpTa8ss4M4LFWWZ0ZpqZNzrY33Mb7KlRBz-xmixEWxZGpiNCFrpSKzxlL-EI-hVATyFDz2Mpr90CjMeBx8ia_EVq8oK_JEmmdUkzndI1AO_x7bzGOZ7JE2frN0vugDGRhuTxWuZVTpZaJIlcSqEsFgtu5GovLckrYzFLk8OFHLE6z2Xt9sHCPgyPI-m2cBssmkm62UZppQSUWX5xuO4tdV5kYi1tDagss2qF9EximVWlADyu6JjARaKQKo8QQP1LXEogCSl0ViudyzjraP3VsQUo_UU05HcoA7MQgFLYqgRjJk1zQRfj-K8I3ikvIAOtuqNdbpWJUzFyj2_WwxfA5Jf8-np-C3P4XPCw3z_1_fMkgFKdDs7664_hIDhPQijU6SA47dcwD8_XPqt9Pi8BDsiIXrCwf-E5ICNIkdCAhd7tOVQooOAKNUpCiiGY9hMrsWMM3yFcwJKwo9wjnjUEDDC2KPG4HtIA7HAI77G3b6kxc__WG-Jy6DVMiCt7p0EmyGuhy1SS1-1h5E-xIu9EQcJT4oejs7ORH5LffyV_vB-T0A_PNpR25ztcZuyGJ8MiLoEJ1BumQhmKybyZIXLGlnTmod8EvFZYHeHMsTGitGTCebpZZr3tM_mJk21AbxuRDB9Qj36bjaA3vnuc-6w3w8YJXKj_ICJ9HHHzIOJmJ2LMoT3oXLpiSfYJy5XcelvL-Hbw2Jo6q0zIFJsLywOoTtuGHPcRdMUc7OiEtQJ7W6gp1GfKei3dp16Pbft4ikEYdcmTfnqssO3aXV-9gtbo92lwcn1NJ40XZlRGPmYEtEsF7Ib6s3cTcGqPweKdzHB-GfLLoakWBnG4ARjaxTczqqpclDH0CL1s8t0rNb8Mh6XW1tC8yqwsQKGllaKTuNZp_uEDlQ3BpctAE7jrSmC3KrejBLgDZAESh8_T5YomVAL1mfKeqN3IHfPLJhIMSlsCGwCCS62sVJVoDY9xfaezCpWBxBZ2BJDh_qzXoJxiU8wbIKE35KYvtknACa6ojuRkwHGhm3KUE2oE_OvSihU2mmlK0CXYdidKeynizxspwm3M5nUiLOrZKg_phI3ZjE1CHrqSHbpEtt3vZAtEYLvPrN-fDEyVU3iQpE86nfHZ-GERHA0mxxNQqKbr8dwFiPhdHpefUVYymbMJf8YuxjzwmVO30Pe3qSziFfebbxAk_weiKP3OIWvU4P5OZqDDPnkBwps7CoJYPrrtxZit8YxJ6FAD8dw11w_Ma59vdfQUdBQX6x8tHjbVd0rpFoqgVdhGWfeKkIPQbueHLdWKgBWh04Bgl1k-lj_AR8WLoF-Ejgf_Vpzfl1XTK6nWPFY1dQ0gd7hvTMd9xWRDexf0gFoQDxniAkK-yc3hj7M5hE7adJp7Puocx0ms5SaygUz67CnW-imDkTkPBkd1p7e0a20ZUmmHB__Di_E_vBf_8WvxYP_wRldkGSvS_MRZ4U8KEkMj63t4lYCegMvfpmFU5g==&lang=sage&interacts=eJyLjgUAARUAuQ==