hermann on Fri, 01 Dec 2023 09:14:15 +0100

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

Re: foursquares.gp

On 2023-11-19 00:28, hermann@stamm-wilbrandt.de wrote:
Bill did develop and tuned foursquares.gp based on this thread:

You can find foursquares.gp in contributed GP scripts section:

Bill's implementation of "twosquares()" in foursquares.gp:


I looked up source code, and one of the first steps is to factor n.
This is an option for small RSA-59, but does not work for next
RSA number =1 (mod 4), RSA-129 takes endless time:
(3:11:10h on 12T 7600X CPU with multithreaded cado-nfs.py)

Is there any other more performant method to find (one) sum of squares
for semiprime of two primes, each =1 (mod 4)?

I know that determining both such sums (ther are exactly two) allows to factor easily. But knowing one does not allow to factor, so can it be computed efficiently?


hermann@7950x:~/RSA_numbers_factored/pari$ gp -q foursquares.gp RSA_numbers_factored.gp
? [l,n]=RSA.get(59);
? twosquares(n)
[250662312444502854557140314865, 93861205413769670113229603198]
? ##
  ***   last result computed in 1,584 ms.
? foreach(RSA.factored(1),r,[l,n]=r;print1(l," ");)
59 129 130 155 160 180 190 640 220 230 768 250