|
Bill Allombert on Tue, 06 Jun 2023 23:38:18 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: Abnormous memory use for gaussian gcd()?
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: Abnormous memory use for gaussian gcd()?
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Tue, 6 Jun 2023 23:33:17 +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=1686087187; c=relaxed/relaxed; bh=qSLdwztZfpvVztrdlHC0/BPqgFj+fI6eHqKfHS1B0qE=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=mnIP6+KQO+QF/lc83j6pJln9TBGhJq8Jl3GywBVINfKM1HM7zpjmCjMPa6eNjVs12+keU8UY8Loy2P0M9jugT9bOWBVPB9IbjtfoveZTU+gw2j7fBj8h4nSXMhl3UyxClMz+AdDAoxv7ezQiQTDvb5WakzDlfapmMI8sWCj7IviyxA+5KF0L0GjDq+OL1RbBRPlOcazJtbsTbmsikdJh1vSLACxQIB7a8rVa3HoNVkAt1Fr3oinQ87HI95fhd6RjrPa901F54jnV0NVRBU0yY6I9zKtxheMuLcBqmBE0y3YV3pih9U+31CDpMu73gA4WPncqD1wwNyMofO8Z8VADpWsz1KtHe8UEkVAK0jvXEoVOGDa6HlmFVPdYJiAC5eMTIwt3qsnlwWPTGYYdmPixfln8ceIy4fRJ1IS6ZAYVH65MToamGiem3xk+B8i89bSn7x7QiYZ6S8RKakjp1f8kJRj/ts1KCWpsHK0lIh1TQl6ePlbKDjOb0duy2xzM7ZAe5myfL64WhqFUBTLGIJJ2rqejoS+0ntUoWQWeBP46HnguiHST/9CuHXN5p5ZKV37pzeI1EwimFTqOfZggfMCALGeu32j1YkhJo01NJHCSx6mQUdK5dOxonwaPzsnXVSfe8nNGET3Hh/ylRL932/QXxVbv9tHsC6wR8ffq2+tfqIg=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1686087187; cv=none; b=kXwccuuUmhG4Oah7bdez5Yl8jWWBqmwwyzLYfj+Vp/fTwx5yPA7Ef1U6BqVjd+D30G5/OlDZYTvFTcY1l4xT+6JbLcYOpuq9M5kVOUwoXsO+TBwnTiO+1DNEeP05nJvr6EfbFH3UpnxqzsZqjkotdLHwj+Lc+cSsljMXbLJybrDP5joYApLxu4vIzs6Nwm/jkyTjXGmbNNQXfrtJeNv8t76NjdChMRNu3Caq2z9VmLAxmZdS7Yvg2SsHHDaK9bixo4FHHlyUtE9G89oUjhMMxPzCC/00yc2mGv1WYjah1KtVUy594wqrm/cMs2U5ELmUvuOdeeD/Xz3dinNgbgYEEsFXCmV4spLbESOuQQgLz+8yisIEfeI9Vuj0OBz/YtNviTXw5OeCO9W19JObxwcuqyI6NIC3TC3YodAb7pMylBvOsLWEEIM+d5OqsoJjBoKvhx6sfFMUdW66s1s94JDmFG1XHjr9t8L4DFhiV5ysVq327y9krptqNuNTYktAWak7qt3+bLZjeGnNsla1w/9q7naTS9NdCe/A5Pbkr99/A0Dng86yqxLraAeb1bBm28Nc8A/t4HLFvZ6XiU/Zjv1PngFYnN1CQ2/EsNAqHTQbTtcRwB7qKnlSBY7WToy9LBTMWUqv5DnDREKLQWrxk4hddeC17FoysCdu6APXGgSYk/0=
- Authentication-results: smail; dmarc=none header.from=math.u-bordeaux.fr
- Authentication-results: smail; arc=none
- Delivery-date: Tue, 06 Jun 2023 23:38:18 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1686087187; bh=qSLdwztZfpvVztrdlHC0/BPqgFj+fI6eHqKfHS1B0qE=; h=Date:From:To:Subject:References:In-Reply-To:From; b=RRDRc7ZEyDC3M3P3hZLlFPbqIjJ6p1YXrjST0px/EhUVW3k13EC/bpEwQRywjXrre pzDUeQ4wV4ol3DUIWlDKMWBVt4gInrNkfxQJRRfvZudugYs0AgMFyPvPbkZQGJiZOL x1kAK3viuHGTGLecA91NS29jqfpdhHAgDfnDVfOJn7gmokBGx1Bs6D5V+JwVKTJ9zq plW0i1YXPt8U3t5WTNarjJDT0DhKRFkaSiwy/b5wfI3UJcUcrcfrcJLGbKYR3gzc17 itxUp0cGeShP5HChSPz1PjlaTsVp1tJPX6C1HsMagLLJkekok+FBRG4SsAIDgbxye8 YnCaehCIzkAZ/BhpiM/IerOF0dnnFn1DMOOHhZps7Q2j6KekO33zh49vcdCsPbrZUY 3UXwU714e8SxaIwLr8/qVTnCFgZBGItkhLeEkEcadn+jmf0sNI0tcRCGcGVmg/p+cI /AbEPuhOu2Sin9wNDoaa1SjCSXErAFDp5ubBv7yK4fv07QfeLLyF8NgxogNign7uKQ Puplh3rX9R7cEUhiG9yKjSVh0yOHp+UpEj+79KsfV54En2qiQCsX9S6e51FTTVTpSZ TrS19CQVuKM6bzf5g9jhJ55W1IZaWCjrcTZyFaXtDKhCUpVqqCNkNpYTfXb/2a80h9 lqS+RYxGNsL4bStnkMznUta0=
- In-reply-to: <14fb32efc08ccda94006a5d745d037d4@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <85b829f5974500a9215307f172e05724@stamm-wilbrandt.de> <ZH4K05Ocjnpj2L8M@seventeen> <5601edb4464767069d9f9c5138a2867e@stamm-wilbrandt.de> <c50d16c794bbe0f7854119c7732cbaa2@stamm-wilbrandt.de> <ZH4+sminS6Dl7iBw@seventeen> <29f5f72b12eddcca3bc96e8b8feb05a7@stamm-wilbrandt.de> <ZH87VbDWIsbSkKYx@seventeen> <14fb32efc08ccda94006a5d745d037d4@stamm-wilbrandt.de>
On Tue, Jun 06, 2023 at 09:36:21PM +0200, hermann@stamm-wilbrandt.de wrote:
> So thanks for fixing gcd() and for the master branch git pointers.
>
> But I have to thank the most for your halfgcd() tip.
> I used gcd(p, sqrtm1+I) to determine (unique) sum of squares for prime p.
> halfgcd(sqrtm1, p) does compute something different than gcd().
> But it allows to determine sum of squares as well.
> In 87ms(!!!) yesterday for 388342-digit prime:
> https://pari.math.u-bordeaux.fr/archives/pari-users-2306/msg00011.html
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/388342.halfgcd.gp
>
> That is so cool, with your gcd() fix halgcd() became even faster!
Indeed, the master branch includes several changes to speed up halfgcd.
However they predate the change to gcd which is unrelated.
But what I do not quite understand is how do you get the squareroots.
If you need to compute them, you can as well use qfbcornacchia directly.
(once you have a solution a^2+b^2=p, you can recover the square root
with a/b mod p).
Cheers,
Bill