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.