hermann on Fri, 06 Oct 2023 11:21:25 +0200


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

Re: efficient foursquare() and/or threesquare1m4() functions 

On 2023-10-06 10:38, Bill Allombert wrote:


Sorry, I mixed P and n, it should be

foursquarep(n)=
{
  for(i=1,sqrtint(n),
    my(P=n-i^2);
    if(P%8!=7 && ispseudoprime(P),return(concat(i,threesquare(P)))))
}


foursquaref(n)=
{
  for(i=1,sqrtint(n),
    my(P=n-i^2, v = valuation(P,2)\2);
    if (P/4^v%8!=7,
      my(F=factor(P,2^20)[,1]);
      if(ispseudoprime(F[#F]),
        return(concat(i,threesquare(P))))));
}


This one is OK.
Cheers,
Bill.


THANK YOU!
This one is not only OK, but very fast.

I added an example use to RSA_numbers_factored repo:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/all_rsa.foursquare.gp
It is so fast, it does determine sum of four squares for all 56 RSA numbers 
in the repo in less than 26 seconds, on a Raspberry computer!
(with assertion on all results being correct)
pi@raspberrypi400:~/RSA_numbers_factored/pari $ gp -q < all_rsa.foursquare.gp 
(n)->for(i=1,sqrtint(n),my(P=n-i^2);if(P%8!=7&&ispseudoprime(P),return(concat(i,threesquare(P)))))
59 [60, 243487708530173787142860315305, 111154201704103703341349614702, 0]~ 79 [2046, 14328643776045048475350894261333941769, 14328643776045048475350894261333941769, 2700566389708041334802487158890593204979]~ 100 [264, 27533584273215645320403924232357590433219276527309, 27533584273215645320403924232357590433219276527309, 2531501937980204088598814147936631992284277784941]~ 
...
...
500 [3498, 4028843608251774938877652691088834356362678678708848968984745846488682043430745851100037515757258094494988724059104478983731162718407606513771181454325159307322274321528263345526270896088487619264745746278722944150605399134421256502359370019698410866, 1655403430507223877348447101652522642606504057262773567359065861382153532649850373974841999500395663684933682561000556456237118051291848305048870706580112647484169616061192886154311549054779296110675635325328070578629793153178862004920499053521992299, 0]~ 617 [7464, 95315287948735494190713283258130633526192725379948697856533626506778978153412848504966648943921369819516203099268986213176108525261011185255002186608094477416998609141630978686524021831121274735320621161640718783192667716697241339311165483452435047512752138534962202163617611658324246977712848852216141190351, 116691032976123115908837326566827027293437300267420386502278353080096485944633990739371935875176726705874410096862160989506211691623181683241310904543701992457989009379930341441641467957808157000616952864956163470329834542180448778246587688094588757004652753182201137720878554563371865938343499722821678585394, 0]~ 2048 [28, 158197984288196117699097355897947500264458455190848222964138664214873348733353898043756194523483689509093385743402168573089458743256253901017830264069606012704497883085623209455523704906878923700142603965513457096959088734082854043425944788477935555382589380809038501009740812793032665236884977009980514922487, 13011773238477059231321994244187743729468594581843753487082884034603212622185946597112257777907861613001484624197063577339843512098442794834693496703933881475402708427339094714589624392731377779402228770755581888942318831433232790010161732825667949844267841944332119616646371761146340753071052451512068626398, 0]~ 
  ***   last result: cpu time 25,881 ms, real time 24,965 ms.
all asserts OK
pi@raspberrypi400:~/RSA_numbers_factored/pari $


Regards,

Hermann.