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

[hermann@stamm-wilbrandt.de]

On 2026-09-25 23:06, Bill Allombert wrote:
> On Fri, Sep 25, 2026 at 11:00:08AM +0200, hermann@stamm-wilbrandt.de 
> wrote:
...
> > 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
Thank you. I tried to change implementation based on your statement but 
failed. So I worked with Gemini again, and got it working with 
qfbsolve(), without qfbredsl2() and CRT:

https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp#L241-L303

The demo output for all 27 factored sofar RSA numbers did show a problem 
for RSA-230 and RSA-768 and a small second commit was needed to really 
return a valid factoring s1,s2 pair:

            \\ Force structural distinctness.
            \\ If C=1 (D=-4), explicitly prevent selecting the [y, x] 
permutation


Finally my little test over the 27 factored RSA numbers got corrected 
from Gemini as well. While doing Euler factorization with s1+s2 only 
worked, it is not guaranteed and in case of p==1 or p==n, gcd() with 
s1-s2 in addition is needed for correct factoring.

Before all these changes I had changed the code to always return monic 
diagonal quadratic binary forms [Qfb(1,0,z)], much simpler and really 
nice:

hermann@8840hs:~/RSA_numbers_factored/pari$ gp -q 
RSA_numbers_factored.gp
? foreach(RSA.factored(),t,my([l,n]=t);my([D,Q,s1,s2]=RSA.qfb_sums(t));\
my(p=gcd(qfeval(Q,s1+s2),n)); if(p==1||p==n,p=gcd(qfeval(Q,s1-s2),n));\
print(l," ",D," ",Q," ",qfeval(Q,s1)==n&&qfeval(Q,s2)==n," 
",1<p&&p<n&&n%p==0))
59 -4 Qfb(1, 0, 1) 1 1
79 -24 Qfb(1, 0, 6) 1 1
100 -520 Qfb(1, 0, 130) 1 1
110 -232 Qfb(1, 0, 58) 1 1
120 -24 Qfb(1, 0, 6) 1 1
129 -4 Qfb(1, 0, 1) 1 1
130 -132 Qfb(1, 0, 33) 1 1
140 -11640 Qfb(1, 0, 2910) 1 1
150 -232 Qfb(1, 0, 58) 1 1
155 -24 Qfb(1, 0, 6) 1 1
160 -376 Qfb(1, 0, 94) 1 1
170 -24 Qfb(1, 0, 6) 1 1
576 -40 Qfb(1, 0, 10) 1 1
180 -4 Qfb(1, 0, 1) 1 1
190 -24 Qfb(1, 0, 6) 1 1
640 -8 Qfb(1, 0, 2) 1 1
200 -24 Qfb(1, 0, 6) 1 1
210 -8 Qfb(1, 0, 2) 1 1
704 -24 Qfb(1, 0, 6) 1 1
220 -20 Qfb(1, 0, 5) 1 1
230 -4 Qfb(1, 0, 1) 1 1
232 -24 Qfb(1, 0, 6) 1 1
768 -4 Qfb(1, 0, 1) 1 1
240 -40 Qfb(1, 0, 10) 1 1
250 -228 Qfb(1, 0, 57) 1 1
260 -24 Qfb(1, 0, 6) 1 1
896 -88 Qfb(1, 0, 22) 1 1
?

Regards,

Hermann.