|
Georgi Guninski on Thu, 16 Oct 2025 17:26:36 +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: Thu, 16 Oct 2025 18:26:11 +0300
- Delivery-date: Thu, 16 Oct 2025 17:26:36 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760628394; x=1761233194; 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=/M1ERAJ2kBYsH5K9Hmf+0CWGtruU5F4PAgRkPw1IKzA=; b=OwuAKnnUClzweyOKyUowcw8L7XDYMCSnohf4PUoOOZf1IsPzJmpOqSMqMlLBtmbuu/ P+AnC3Y1Q2va6TeYOq0PQaSz8gYQS7p9pgnVhF4S5GcCeZ58wNuLjhHSiYwqLuZdFCcQ fF2SNg3MkHiiMtEdaYXcYuXvrkqy6HBcgk5qESKgCOlhM7gtNf5zoYZ1LrDni87QSYQr m8C4BvvFoyUcQr0/JI06JEQKUBkOPl7t8RrafBPthVOodO3wlxgWPuKkCQHPRp6Mdd+h j9bJHQbewoFzLd4eMGzUT4BZgdM+nNc+dk4E0hwUlBbOjhAA0zaAx4rQdhQhnCAXt2Oq WhYQ==
- In-reply-to: <aNgAbledzvkseXAJ@seventeen>
- References: <CAGUWgD9wSzZpdZvDw6jiqPc6aNUfv=iX7=YzCyH=OUgNBqNDxA@mail.gmail.com> <aNgAbledzvkseXAJ@seventeen>
>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]