Re: question on intersection of two primes discriminant search for qfb

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Sep 25, 2026 at 11:00:08AM +0200, hermann@stamm-wilbrandt.de wrote:
> It is well known that one can easily factor a semiprime if given two
> distinct sums of two squares:
> 
> pi@raspberrypi5:~/RSA_numbers_factored/pari $ gp -q RSA_numbers_factored.gp
> ? t=RSA.get(768); n=t[2]; [e,f]=RSA.square_sums(t);[a,b]=e;[c,d]=f;
> ? [(a^2+b^2)==n && (c^2+d^2)==n, #Set([a,b,c,d])]
> [1, 4]
> $
> 
> ? p=gcd((a+c)^2+(b+d)^2,n); q=gcd((a+c)^2+(b-d)^2,n);
> ? [1<p && p<n && 1<q && q<n && n==p*q, #binary(n)]
> [1, 768]
> ?
> 
> In lecture free period I worked Heidelberg University elementary number
> theory
> lecture from fall 2024 with videos, script and exercises. Followed by
> 53×30min
> youtube video lecture series "Berkeley math 115: Introduction to number
> theory",
> here my summaries with link to youtube and my code examples:
> https://github.com/Hermann-SW/uni-heidelberg/blob/main/markdown/Math155.md
> 
> 
> I learned on quadratic binary forms in Berkley lecture, and thought on
> generalization for sum of two squares approach shown above [which is
> Qfb(1,0,1)].
> 
> In a many hour chat with Gemini I was finally able to get working code,
> and it is short and cleaner than all we had worked on in between.
> In between was code with number fields, t_POL and finally qfbs.
> 
> Here is new function qfb_sums(), only 31 lines are result of the Gemini
> chat:
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp#L241-L296
> 
> Any comments on that code with a loop through all negative discriminants
> aborting if
> conditions on determined qbfs for p and q are met are welcome (this email is
> for that).

It seems to me you are reimplementing qfbsolve.
(I added qfbredsl2 for the purpose of writing qfbsolve)

If RSA=p*q, once you have found D<0 such that both p and q split, then you can try
qfbsolve(qfbprimeform(D,1),[p,1;q,1],1)

Cheers,
Bill