hermann on Fri, 06 Oct 2023 01:06:39 +0200


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

efficient foursquare() and/or threesquare1m4() functions


In this posting Bill provided function "foursquare(n)":
https://pari.math.u-bordeaux.fr/archives/pari-users-2310/msg00004.html

foursquare(n) = abs(qfsolve(matdiagonal([1,1,1,1,-n]))[1..4]);

It has interesting property wrt odd semiprimes being product of two primes =1 (mod 4):

$ cat sem.gp
foursquare(n) = abs(qfsolve(matdiagonal([1,1,1,1,-n]))[1..4]);

isdistinctsemiprime1m4s(n)={
  my(f=factor(n));
  return(#f[,1]==2&&f[,2]==[1,1]~&&f[1,1]%4==1&&f[2,1]%4==1);
}

mx=eval(getenv("mx"));
forstep(i=5,mx,4,if(isdistinctsemiprime1m4s(i),print(i,",",foursquare(i))));
$

Always the first two entries seem to be 0s:

$ mx=300 gp -q < sem.gp
65,[0, 0, 7, 4]~
85,[0, 0, 2, 9]~
145,[0, 0, 9, 8]~
185,[0, 0, 4, 13]~
205,[0, 0, 13, 6]~
221,[0, 0, 10, 11]~
265,[0, 0, 11, 12]~
$

$ mx=1000000 gp -q < sem.gp | grep -v '\[0, 0'
$


I asked for foursquare() for applying to unfactored RSA-numbers =1 (mod 4) > RSA-250. Unfortunately that is not possible, since qfsolve() does first factor the determinant
of passed matrix, which is -n. Find details in P.S: of this posting:
https://www.mersenneforum.org/showthread.php?t=28910

Same posting is on Lagrange's three square theorem.
I describe there how I found original 1798 french text online on internet archive.

I am not sure how to make foursquare(n) efficient (faster than factoring n). Perhaps the prove of theorem "Odd integer not being 8n+7 is sum of 3 squares"
on page 398 will help to get efficient threesquare1m4(n).
Difficult to say, since I don't speak French (although I was able to understand
"Tout nombre impair, ... quarrés." theorem give the context).

Any ideas for efficient foursquare() and/or threesquare1m4() are welcome.
I want to apply to these unfactored RSA-numbers =1 (mod 4):

$ gp -q RSA_numbers_factored.gp
? foreach(RSA.unfactored(1),r,[l,n]=r;print1(l," "))
280 309 310 320 340 360 370 390 400 430 450 460 1536 470 500 617 2048
?

Regards,

Hermann.