|
Bill Allombert on Fri, 06 Oct 2023 16:04:41 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: efficient foursquare() and/or threesquare1m4() functions
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: efficient foursquare() and/or threesquare1m4() functions
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Fri, 6 Oct 2023 16:04:11 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1696601043; c=relaxed/relaxed; bh=j68WrU31z/TZdzedMBxgOr2M+zRG4ZMmaqvwMJ9cORs=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=3sUMKfaCZO4JKX1Csxp9FU8LXZSgByUaAl+OsqX7dKI+0iwdC0Q+Oq+Nc01nRXyHRU7ZL6cnKtxomokl9XInTkwzY0sddkyQggjWIn+Les/lYC+Z7YrlhSH9yO8LISqOZb4z79BS3VYkXJgRBZFD6U/fX5wRp3jrfNQQJO59YMb9kh5eqSR5npFObZ7bWaUQftBFrQM4GJT6cyQYrYtEzcbvoZDAoMHZYCzr/y8df8/yt26qpRgB4CA/3/oYnw7xmqSdZ1Pqyg0SR06pdl5kqJsF8rQyonzjLzGV3MvPEMZRq4GLetThmoI0Rr7UsDPF9a8HRDhF8iGxE9I9NtnGP7kXl7ESkxndCBGMFw8Lm7MtrfPG677ZrUVcTM/Vq4jB/57Gy0BpCxVz6AVs0s72yV+uJJj2spH1VgQixRdGi9n3MzeBvJhLxv5XuuniRDpjCdxsn9rZ/M4irJLnEvj7Vi1D4AhCrW8P94OepFKX8dwnV9ISdnzurwFQqiONWhTk0wMwiezC8ldZR1bTz4JzTIkVQ3cPR1Rleh8ZsP9GO5C4fwoNluwKOEsV1aZqWQwycqUXeVGYqDtBhY9Ym/eUrFcoPEU+JVnFoz8WgxAAoRFTKfyrabJ2nipOyqViL2HBpHD5B9qc2BaqTg++dY3RoHo3TUlNpCB0x3YZkHSWPso=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1696601043; cv=none; b=mVNzciGdY9hHYuUSafV+ANNtrE4vPOw5v/SI6rNIJ6Gg1D8t9FxZ0KLke+Qz4H4XNWI8MzZw2mlkkwNdw/M7T+/BpGG68bqlmu1NxwHCNXmp7QUlXRotoZpcz6rAfhyAB0ReG2/9akyaDwnPr4baz1NpHJvvBKgP3Rq1uHNX+U/NQRGLO8hT/lmXqO4e/s4dkIYMoe8gQW/qqBH4tMFFAOQ7ow4LIOKBuPbBCMrcQLVIzp0RkWXR+ewtpnA/6uHNHSd86k4CSXQgZdo2sBytIx3JouP5dXdeUxHCzdwqj1qXraDAjumVzXbYZk/LGC1iflcCivXhM1XbmrZcz/WbuSvwU5uprrDbzf2CU1XNclIXEm5DKyEhK6WqrB0lbTke03jLbhdyww1teF5NWznpx8csQ9FPXuYeQUBtEhC9upP9sWNfPpLkqYrWBSNG+jUfDZ2nlzA14vQ4D+5MFEcvZoAmYRipX+uO4MvXRjVlp5ziz+RSp9AKnmmH6XieYADhWm9UOZ5qM9Wn3P/wOebydqOd6GTEng8w6wYpKZ/BzIxhX10FPJ0ZjsoEAI6LA5KmCvVSk/PtUzPC52Sd3CIwCo2TQghv8YKSkrgkWBw+e+npw5+AME8JnsBLBT6a1VXW/UySj1+LgkmKRovsRIUWCzjCPL+hNuGNZKfUtKxOILs=
- Authentication-results: smail; arc=none
- Delivery-date: Fri, 06 Oct 2023 16:04:41 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1696601043; bh=j68WrU31z/TZdzedMBxgOr2M+zRG4ZMmaqvwMJ9cORs=; h=Date:From:To:Subject:References:In-Reply-To:From; b=HjeQzJHFeSt3gwa1iVvWf/GunPYT6dxLIs8ciSI6BQTyr2Ck9v7lLRVq3ZVO+mJoV ++DM6xG07Z7HyUG3pLxww8kDshP/ny2GPLaF87dlgyZpYoNyflIMlDjhRExJi/nSks BPenJKKsDjvKRmUMnVLEm+GUF18gAgA2mxW12OG9GpAX/nvKlKzpUr1/oI01lZTED5 3g3V5lr2JqLy+obDMwMGhDSDqhqVndii4j4JyvQzoqlLYyRjjvsyUyRRmKuxZeGKn7 wuu7B5numDhxRaMRTCj+3J/rvuPBN7CAUfI9Zx51TTu3GAmWzpSHjl4j7RgfD82+YA RArC2RH33gOaxzw+nRPtGdN0I+mniErGOXz831+96OEB5Sp7tA8nocA2TwcW8TM8Zz TIYEoY/SRgU+kNpF/VZoX9KAxpw7Uasm69LBwNgCsc2I1lJNGT/kg3sqWLSRp6zzxU AqxedvGM0akM+EM5MPCsfjql0EfYWvB17wnwGmwRg6rJK04A8AqOJ+bb5N9hlygO6b rOC7naxP+ev4FzZSlRIlUvicaKflAsK9p4/PrhhcLKxsUQOeOntHtDpmp7YuKOM7yr W57EpyV4cpMB4T9tn67kymIOZY1oBytMTHagKGzOdc7Ekpi+mRD6+nduxG6q8+1br/ YwNPe25nA9rqcfCbUOLMxma8=
- In-reply-to: <ZR/HnWWiyARDRhLM@seventeen>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <d1c78430066dfb66eb8919b4cde59d9c@stamm-wilbrandt.de> <ZR/CnVFCjw69Ukyc@seventeen> <ZR/HnWWiyARDRhLM@seventeen>
On Fri, Oct 06, 2023 at 10:38:53AM +0200, Bill Allombert wrote:
> > 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.
... but suboptimal, we should start by the largest i, so that P is as
small as possible!
foursquaref(n)=
{
forstep(i=sqrtint(n),1,-1,
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))))));
}
Cheers,
Bill.