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

[Georgi Guninski <gguninski@gmail.com>]

>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);

It works for special cases like f=x^D+SMALL and g=y^D+small for solutions
y ~ x^2 and even y ~ x^4 :). From the attached sage script:

f1=x^3+3;f2=y^3+5;x0=next_prime(2^128);y0=next_prime(2^256);n=(f1*f2)(x0,y0)
ss=guninski_fg(n,f1,f2,L=100,allsols=False,prot=1);ss

L= 100  log_2(L) 6
Solution at ro= 0 log_2(g)= [384]
[39402006196394479212279040100143613822795928923774824567754654110574971675702741574341355383326638055807424179340846]

f1=x^5+3;f2=y^5+5;x0=next_prime(2^128);y0=next_prime(2^(4*128));n=(f1*f2)(x0,y0)
ss=guninski_fg(n,f1,f2,L=10**4,allsols=False,prot=1);ss
L= 10000  log_2(L) 13
Solution at ro= 0 log_2(g)= [640]