Apologies for OT, but this might be of interest.
>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.
1. Is this correct?
2. Is this known?
3. Can it be improved?
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]
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
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion visit
https://groups.google.com/d/msgid/sage-devel/CAGUWgD8ja0byswRDTOK21oiLz5qnT_3qzj%3D99Q8rcBkRMg%2BFsA%40mail.gmail.com.
"""
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
