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

Georgi Guninski on Sun, 28 Sep 2025 16:09:28 +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: pari-dev@pari.math.u-bordeaux.fr
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: Georgi Guninski <gguninski@gmail.com>
Date: Sun, 28 Sep 2025 17:08:56 +0300
Delivery-date: Sun, 28 Sep 2025 16:09:28 +0200
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1759068566; x=1759673366; darn=pari.math.u-bordeaux.fr; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=/AKQU76kIvG0rDIeWo4kieIyJv6M0AKykHq6e5yhRF0=; b=Bpqd4gU3aM8UQty3uQSXp/lQJQO0lCbsqbFhJv0RNlj42m7B/438PJe2h1hsj1RCXR OXVqB2AiyETe5URNNBnDVjIx/6WZ40mjDY90nBiYEYU/sSPkgdHrAY7QSBXSjDUALl/7 QU6M3H7OAp29Msq+OIp9Nnv4uHkWB9PlG1UOx8rX/ktfAys6dWWrJFtnwwvl17HmdZ4r nFq2pxJwGGIJwfVaHOjseBoL53GYq/vOLKI2Mb5kEirtgAKUoV2/zD5cEz9YRwhWRkxS jx+7heEvDWemSP8v2mUZWF18ZZNgWeypbfX+A1xPeBKf9TTdGMjwDfwatva34zg41bUs tRhw==
In-reply-to: <aNgAbledzvkseXAJ@seventeen>
References: <CAGUWgD9wSzZpdZvDw6jiqPc6aNUfv=iX7=YzCyH=OUgNBqNDxA@mail.gmail.com> <aNgAbledzvkseXAJ@seventeen>

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: Watson Ladd <watsonbladd@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>