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

--0000000000004978d3063fde063a
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

You may be interested in Coppersmith's method with application to RSA.
While not identical some of the ideas apply.

In particular we can think of x and y the same size as x and v, where y=3Dx=
+v
and v is small. Then knowing that x must be close to a given real number we
end up hunting for u,v small that solve a certain polynomial over the
integers.


---
Astra mortemque praestare gradatim

On Sun, Sep 28, 2025, 7:18=E2=80=AFAM Georgi Guninski <[email protected]>=
 wrote:

> Many thanks for the feedback!
>
> I am looking for coauthors for a generalization of this algorithm.
>
> Regarding your answer:
>
> >n^(1/D) - (x*y) =3D a_{D-2}*y/x/D + b_{D-2}*x/y/D +...
> >so as long as x/y~1 and C small this should work but I do not expect you=
r
>
> The algorithm works for x/y>20.
>
> > but I do not expect your algorithm to work if x ~ sqrt(y), for example
>
> This is explained in the paper, x,y must of the same size,
> something like |log(x)-log(y)|<4.
> The current implementation fails for x ~ sqrt(y) in general.
>
>

--0000000000004978d3063fde063a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div>You may be interested in Coppersmith&#39;s meth=
od with application to RSA. While not identical some of the ideas apply.</d=
iv><div dir=3D"auto"><br></div><div dir=3D"auto">In particular we can think=
 of x and y the same size as x and v, where y=3Dx+v and v is small. Then kn=
owing that x must be close to a given real number we end up hunting for u,v=
 small that solve a certain polynomial over the integers.</div><div dir=3D"=
auto"><br></div><div dir=3D"auto"><br></div><div>---</div><div data-smartma=
il=3D"gmail_signature"><div dir=3D"ltr">Astra mortemque praestare gradatim<=
/div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_a=
ttr">On Sun, Sep 28, 2025, 7:18=E2=80=AFAM Georgi Guninski &lt;<a href=3D"m=
ailto:[email protected]" rel=3D"noreferrer noreferrer" target=3D"_blank">=
[email protected]</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex">Many thanks for the feedback!<br>
<br>
I am looking for coauthors for a generalization of this algorithm.<br>
<br>
Regarding your answer:<br>
<br>
&gt;n^(1/D) - (x*y) =3D a_{D-2}*y/x/D + b_{D-2}*x/y/D +...<br>
&gt;so as long as x/y~1 and C small this should work but I do not expect yo=
ur<br>
<br>
The algorithm works for x/y&gt;20.<br>
<br>
&gt; but I do not expect your algorithm to work if x ~ sqrt(y), for example=
<br>
<br>
This is explained in the paper, x,y must of the same size,<br>
something like |log(x)-log(y)|&lt;4.<br>
The current implementation fails for x ~ sqrt(y) in general.<br>
<br>
</blockquote></div>
</div></div>

--0000000000004978d3063fde063a--