Re: [OT] On factoring integers of the form n=(x^D+1)(y^D+1) and n=(x^D+a

Watson Ladd on Sun, 28 Sep 2025 17:18:03 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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

To: Georgi Guninski <gguninski@gmail.com>
Subject: 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
From: Watson Ladd <watsonbladd@gmail.com>
Date: Sun, 28 Sep 2025 08:17:48 -0700
Cc: pari-dev@pari.math.u-bordeaux.fr
Delivery-date: Sun, 28 Sep 2025 17:18:03 +0200
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1759072681; x=1759677481; darn=pari.math.u-bordeaux.fr; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=gVEmjjMeAjENYWUsg1+SFGFTYVUsUDbxZpkDQN6Detg=; b=gJo6JfL4oXTMcx+thgD3Dmb0uT+qhY2thJmrDUs+8fys+MJ2gY6a3qt3p70imKHWRJ UB22RSDE2Z5v/8gmDZXzRhMRbpBEjsR9IQOqMDLlE/qvqaARKuQCsNY1nTZWngntNH3F NdyTaGIm6JF2lWG5ZJjGhDWOcDOQKE+mk77d6So5IsDKrsSFfs/gm4FVQTSHmmg3OPTm mRqoTy/5rfwrWDW3wz9f2U1nD/mGRoI2mz1e8NalzdlndwUW2qstUGQhCI71M5EiYI7p jt7z+kToe7kNFwHhyJy+9NocxNawZNL7VUE0HundWsONPhBjx5arTZ41iXc8QLaVC79Z fRpw==
In-reply-to: <CAGUWgD9ZBGtrhwSHjC4G5bExWGfWMA2KE-YErCafeBfuoe=a=w@mail.gmail.com>
References: <CAGUWgD9wSzZpdZvDw6jiqPc6aNUfv=iX7=YzCyH=OUgNBqNDxA@mail.gmail.com> <aNgAbledzvkseXAJ@seventeen> <CAGUWgD9ZBGtrhwSHjC4G5bExWGfWMA2KE-YErCafeBfuoe=a=w@mail.gmail.com>

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=x+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 AM Georgi Guninski <gguninski@gmail.com> 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) = 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 your

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.

Follow-Ups:
- 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
  - From: Georgi Guninski <gguninski@gmail.com>

References:
- [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
  - From: Georgi Guninski <gguninski@gmail.com>
- 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
  - From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- 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
  - From: Georgi Guninski <gguninski@gmail.com>