[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

--000000000000c347d6063fc81754
Content-Type: text/plain; charset="UTF-8"

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.

--000000000000c347d6063fc81754
Content-Type: text/plain; charset="US-ASCII"; name="factor_polyn.sage.txt"
Content-Disposition: attachment; filename="factor_polyn.sage.txt"
Content-Transfer-Encoding: base64
Content-ID: <f_mg2a9ia50>
X-Attachment-Id: f_mg2a9ia50

IiIiCgpzYWdlIGNvZGUgZm9yIHRoZSBwYXBlcjogCgpPbiBmYWN0b3JpbmcgaW50ZWdlcnMgb2Yg
dGhlIGZvcm0gJG49KHheRCsxKSh5XkQrMSkkIGFuZCAkbj0oeF5EK2Ffe0QtMn14XntELTJ9Kysg
Li4uIGFfMCkgKHleRCtiX3tELTJ9eV57RC0yfSsgLi4uIGJfMCkkIHdpdGggJHgseSQgb2YgdGhl
IHNhbWUgc2l6ZQoKaHR0cHM6Ly93d3cucmVzZWFyY2hnYXRlLm5ldC9wdWJsaWNhdGlvbi8zOTU4
Nzc1MDdfT25fZmFjdG9yaW5nX2ludGVnZXJzX29mX3RoZV9mb3JtX25feF9EXzF5X0RfMV9hbmRf
bl94X0RfYV9ELTJfeF9ELTJfYV8wX3lfRF9iX0QtMl95X0QtMl9iXzBfd2l0aF94X3lfb2ZfdGhl
X3NhbWVfc2l6ZQoKCgoiIiIKCmRlZiBndW5pbnNraV9mZyhuLGYsZyxMPU5vbmUscHJvdD1GYWxz
ZSxhbGxzb2xzPUZhbHNlKToKCSIiIgoJbjogaW50ZWdlciB0byBiZSBmYWN0b3IsIEw6ICBib3Vu
ZAoKCWY9eF5EK08oeF4oRC0yKSksZz15XkQrTyh5XkQtMSksIHggfiB5IDw9PiBmbG9vcihsb2co
eF8wKSk9Zmxvb3IobG9nKHlfMCkpCgluPWYoeF8wKSpnKHlfMCkKCglDIGlzIG1heGltdW0gY29l
ZmZpY2llbnQgb2YgZixnIGFuZCBpdCBtdXN0IGJlIHNtYWxsIGZvciBlZmZpY2llbmN5CgoJdGhl
IGNvZWZmaWNpZW50IGFfaSBvZiBmIGFuZCBiX2kgb2YgZyBtdXN0IGJlIG5vbm5lZ2F0aXZlCgoJ
Y29tcGxleGl0eSBpbmNsdWRpbmcgZmFpbHVyZTogIE8oQyBsb2dfMihuKSAgdW5pdmFyaWF0ZSBw
b2x5bm9taWFsIGZhY3Rvcml6YXRpb25zIG92ZXIgdGhlIGludGVncmVzKQoJcmV0dXJucyBsaXN0
IG9mIGZhY3RvcnMgb2YgbiBvciBlbXB0eSBvbiBmYWlsdXJlCgoJdXNhZ2U6CgoJS3guPHgseT49
UVFbXQoJCglCPTIqKjQwMDtmMT14XjQrNSp4XjIrMTtmMj15XjQrMTQqeV4yKzI7eDAseTA9W3Jh
bmRpbnQoQiwyKkIpIGZvciBfIGluICgxLDIpXTtuPWYxKHgwLDApKmYyKDAseTApCgkldGltZSBz
cz1ndW5pbnNraV9mZyhuLGYxLGYyLEw9Tm9uZSxhbGxzb2xzPUZhbHNlLHByb3Q9MSkKCXByaW50
KCJsb2coc29sLDIpPSIsUlIoc3NbMF0pLmxvZygyKSkKCglhdXRob3I6ICBHZW9yZ2kgR3VuaW5z
a2kgV2VkIFNlcCAyNCAwMjo1NTowMiBQTSBVVEMgMjAyNQoJIiIiCglzb2xzPVtdCglYLFk9Zi5w
YXJlbnQoKS5nZW5zKCkKCUtYPVFRW3N0cihYKV0KCUQ9Zi5kZWdyZWUoKQoJYXNzZXJ0IEQ9PWcu
ZGVncmVlKCksImcuZGVncmVlKCkgIT0gZi5kZWdyZWUoKSIKCWFzc2VydCBmLmNvZWZmaWNpZW50
KHtYOkQtMX0pPT0wLCJYXihELTEpICE9IDAiCglhc3NlcnQgZy5jb2VmZmljaWVudCh7WTpELTF9
KT09MCwiWV4oRC0xKSAhPSAwIgoJQz1tYXgoW2kgZm9yIGksaiBpbiBmXSkKCUM9bWF4KFtDXStb
aSBmb3IgaSxqIGluIGddKQoJaWYgTCBpcyBOb25lOiAgTD1mbG9vcihDKmxvZyhuLDIpKQoJaWYg
cHJvdDogIHByaW50KCJMPSIsTCwiIGxvZ18yKEwpIixmbG9vcihsb2coTCwyKSkpCglGPWYqZy1u
Cgl0PWZsb29yKEFBKG4pKiooMS9RUShEKSkpCglmb3Igcl8wIGluIHJhbmdlKEwpOgoJCVkxPSh0
LXJfMCkvWAoJCUYyPUYuc3Vicyh7WTpZMX0pCgkJRjI9S1gobnVtZXJhdG9yKEYyKSkKCQlybz1G
Mi5yb290cyhtdWx0aXBsaWNpdGllcz1GYWxzZSkKCQlybz1bWlooaSkgZm9yIGkgaW4gcm8gaWYg
ZGVub21pbmF0b3IoaSk9PTFdCgkJc29sPVtnY2QoZihpLDApLG4pJW4gZm9yIGkgaW4gcm8gaWYg
Z2NkKGYoaSwwKSxuKSVuPjFdCgkJaWYgbm90IHNvbDogIGNvbnRpbnVlCgkJaWYgcHJvdDogIHBy
aW50KCJTb2x1dGlvbiBhdCBybz0iLHJfMCwibG9nXzIoZyk9IixbZmxvb3IoUlIoaSkubG9nKDIp
KSBmb3IgaSBpbiBzb2xdKQoJCXNvbHMgKz0gc29sCgkJc29scz1saXN0KHNldChzb3J0ZWQoc29s
cykpKQoJCWlmIG5vdCBhbGxzb2xzOiAgYnJlYWsKCXJldHVybiBzb2xzCgpkZWYgZ2V0cG9seWRt
MihELEMsWCxEMj0yKToKCSMgZm9yIGd1bmluc2tpX2ZhY3Rvcl9mZwoJcmV0dXJuIFgqKkQrc3Vt
KFgqKmkgKiByYW5kaW50KDAsQykgZm9yIGkgaW4gcmFuZ2UoRC1EMisxKSkKCmRlZiBiZW5jaG1h
cmtfZmcobGltLEQ9MyxCQz0xMCxCPTIqKjIwMCxEMj0yKToKCWJhZD0wCgliYWRzcz0wCglLeC48
eCx5Pj1RUVtdCglpMD0wCgliYWRsPVtdCgl3aGlsZSBpMCA8IGxpbToKCQlmMT1nZXRwb2x5ZG0y
KEQsQkMseCxEMj1EMikKCQlmMj1nZXRwb2x5ZG0yKEQsQkMseSxEMj1EMikKCQl4MD1yYW5kaW50
KEIsNCpCKQoJCXkwPXJhbmRpbnQoQiw0KkIpCgkJI3ByaW50KGYxLGYyKQoJCXAxPWYxKHgwLHkw
KQoJCXAyPWYyKHgwLHkwKQoJCSNpZiBnY2QocDEscDIpICE9IDE6ICBjb250aW51ZQoJCWkwICs9
IDEKCQluPXAxKnAyCgkJc3M9Z3VuaW5za2lfZmcobixmMSxmMixMPU5vbmUsYWxsc29scz1GYWxz
ZSxwcm90PVRydWUpCgkJZ29vPWFueShbZ2NkKGksbiklbiBmb3IgaSBpbiBzcyBpZiBnY2Qobixp
KSVuPjFdKQoJCQoJCWlmIG5vdCBnb286ICAKCQkJYmFkICs9IDEKCQkJYmFkbCArPSBbKG4sRCxm
MSxmMix4MCx5MCldCgkJaWYgbm90IHNzOiAgYmFkc3MgKz0gMQoJCXByaW50KGkwLCdiYWQ9Jyxi
YWQsYmFkc3MsZ29vKQoJCQoJcmV0dXJuIGJhZCxiYWRsCgojWW91IGNhbiB0aGUgY29kZSBpbiBh
IGJyb3dzZXIgYXQ6CiMgaHR0cHM6Ly9zYWdlY2VsbC5zYWdlbWF0aC5vcmcvP3o9ZUp5OVZsRnYy
ellRZms2QV9BZk9TVkhLWmh4SlRkRE5LUXMwTnRLSGVzdlNkcGhUSXhWa20xTFlTcVFnVW8zVm92
dnR1Nk1rT3pINnNHSEFFSWNXZVhmazhidnZQcm5YNngzc0gteVA5VXFRUkpmRTNnbFN4SVVvUndU
WHJ4Uko0cVhWcFZRcGtjcUtWSlNHNk1UNWdYOU9qaFNuNjQtVFFlRFIybjBka1ZpdE5zdHg5RzF5
SEg1ZmYzUmZnd0dKSTk4anpuWFJtT3JXUkJaZ09TTDMwdDZSb3pXcmo3cGpUSnpESUw4S1RPak8y
c0tNVGs3dTctLUhwVEFpTHBkM2FXekZVQWw3VWxTTFRDNWpLN1U2ZWZiTDJjX1BuNV81ejZNckZX
M3VFSFYzaUhRU3dlWVIzaUZTMFRxYVJFR05Rd1RadHd0eEJJbmhFNHlRZG9UMmhadlZib1NFSTB3
WFhPcHVQMHcyNnBMRnYxNEQ4RW9rSksyVVZPYXpqSktVS3Bhd2xFMzViMW9KVnBUYThzczRNNExG
V1daMFpwcVpOenJZMzNNYjdLbFJCei14bWl4RVd4WkdwaU5DRnJwU0t6eGxMLUVJLWhWQVR5RkR6
Mk1wcjkwQ2pNZUJ4OGlhX0VWcThvS19KRW1tZFVrem5kSTFBT194N2J6R09aN0pFMmZyTjB2dWdE
R1JodVR4V3VaVlRwWmFKSWxjU3FFc0ZndHU1R292TGNrcll6RkxrOE9GSExFNnoyWHQ5c0hDUGd5
UEktbTJjQnNzbWttNjJVWnBwUVNVV1g1eHVPNHRkVjVrWWkxdERhZ3NzMnFGOUV4aW1WV2xBRHl1
NkpqQVJhS1FLbzhRUVAxTFhFb2dDU2wwVml1ZHl6anJhUDNWc1FVb19VVTA1SGNvQTdNUWdGTFlx
Z1JqSmsxelFSZmotSzhJM2lrdklBT3R1cU5kYnBXSlV6RnlqMl9Xd3hmQTVKZjgtbnAtQzNQNFhQ
Q3czel8xX2ZNa2dGS2REczc2NjRfaElEaFBRaWpVNlNBNDdkY3dEOF9YUHF0OVBpOEJEc2lJWHJD
d2YtRTVJQ05Ja2RDQWhkN3RPVlFvb09BS05VcENpaUdZOWhNcnNXTU0zeUZjd0pLd285d2pualVF
RERDMktQRzRIdElBN0hBSTc3RzNiNmt4Y19fV0ctSnk2RFZNaUN0N3AwRW15R3VoeTFTUzEtMWg1
RS14SXU5RVFjSlQ0b2VqczdPUkg1TGZmeVZfdkItVDBBX1BOcFIyNXp0Y1p1eUdKOE1pTG9FSjFC
dW1RaG1LeWJ5WklYTEdsblRtb2Q4RXZGWllIZUhNc1RHaXRHVENlYnBaWnIzdE1fbUprMjFBYnh1
UkRCOVFqMzZiamFBM3ZudWMtNnczdzhZSlhLal9JQ0o5SEhIeklPSm1KMkxNb1Qzb1hMcGlTZllK
eTVYY2VsdkwtSGJ3MkpvNnEweklGSnNMeXdPb1R0dUdIUGNSZE1VYzdPaUV0UUo3VzZncDFHZktl
aTNkcDE2UGJmdDRpa0VZZGNtVGZucXNzTzNhWFYtOWd0Ym85Mmx3Y24xTko0MFhabFJHUG1ZRXRF
c0Y3SWI2czNjVGNHcVB3ZUtkekhCLUdmTExvYWtXQm5HNEFSamF4VGN6cXFwY2xESDBDTDFzOHQw
ck5iOE1oNlhXMXRDOHlxd3NRS0dsbGFLVHVOWnBfdUVEbFEzQnBjdEFFN2pyU21DM0tyZWpCTGdE
WkFFU2g4X1Q1WW9tVkFMMW1mS2VxTjNJSGZQTEpoSU1TbHNDR3dDQ1M2MnNWSlZvRFk5eGZhZXpD
cFdCeEJaMkJKRGhfcXpYb0p4aVU4d2JJS0UzNUtZdnRrbkFDYTZvanVSa3dIR2htM0tVRTJvRV9P
dlNpaFUybW1sSzBDWFlkaWRLZXluaXp4c3B3bTNNNW5VaUxPclpLZ19waEkzWmpFMUNIcnFTSGJw
RXR0M3ZaQXRFWUx2UHJOLWZERXlWVTNpUXBFODZuZkhaLUdFUkhBMG14eE5RcUticjhkd0ZpUGhk
SHBlZlVWWXltYk1KZjhZdXhqendtVk8zMFBlM3FTemlGZmViYnhBa193ZWlLUDNPSVd2VTRQNU9a
cUREUG5rQndwczdDb0pZUHJydHhaaXQ4WXhKNkZBRDhkdzExd19NYTU5dmRmUVVkQlFYNng4dEhq
YlZkMHJwRm9xZ1ZkaEdXZmVLa0lQUWJ1ZUhMZFdLZ0JXaDA0QmdsMWstbGpfQVI4V0xvRi1Famdm
X1ZwemZsMVhUSzZuV1BGWTFkUTBnZDdodlRNZDl4V1JEZXhmMGdGb1FEeG5pQWtLLXljM2hqN001
aEU3YWRKcDdQdW9jeDBtczVTYXlnVXo2N0NuVy1pbURrVGtQQmtkMXA3ZTBhMjBaVW1tSEJfX0Rp
X0VfdkJmXzhXdnhZUF93Umxka0dTdlNfTVJaNFU4S0VrTWo2M3Q0bFlDZWdNdmZwbUZVNWc9PSZs
YW5nPXNhZ2UmaW50ZXJhY3RzPWVKeUxqZ1VBQVJVQXVRPT0KCg==
--000000000000c347d6063fc81754--