Georgi Guninski on Sat, 27 Sep 2025 15:08:08 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
[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 |
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==