|
Bill Allombert on Thu, 15 Jun 2023 19:00:19 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: 388342-digit largest known twin prime: faster sum of squares or sqrt(-1) (mod p) ?
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: 388342-digit largest known twin prime: faster sum of squares or sqrt(-1) (mod p) ?
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Thu, 15 Jun 2023 18:55:36 +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=1686848128; c=relaxed/relaxed; bh=gwdenKjQOa5bozDt4yaVaQndyEtW9T+Hx1MMmZzpN4o=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=HU7DyeU8WGBKImYDdUNliRWVIvDOxbrQhehU6W0ItyCMZeObefYejY2owwpU23RIA8FStYWU+eQhLXfIZwlVkqf9EyJRb9Au/rf2QaAVNQ444HIwKHqVST0HQhAYBk0V6/P4LvAIGnxunRpm7StVBEItLEq97bw0O6aG0CZs7nmN5McFrfsIcpT0rMZRUibqfcV81Oq5P7tmYz1jFuflKxhkAwqGOHfL6k0P/cAAP70Te6pmleq/1H5iG5XuUOy40UMXJ6Xbu9aQ9zZEVSPQyT6UCIlxuXzKyI53er3MBZQZLD7QwD1gOn2TbUIdD9AR1SXbNLHuiCDqWHh89SkR8JTkJyfigAwe4tkhZLQ0n8mfEEgXfdW2XKOxzLgD0kfM4Bx59G46dD64fyvBxKt5Mdw0C6gv0WG77JFGTNaYMvFTrldMlOjoaZ9dEx0UsYxrDz+WIL/QrbTdJOvXD8hUcug9mIzHP9Vbd6ZOmlOU40LpLo9JrGLqypjHYYqU8ahYyjc+jFWQ1q5FFcLG/azCtSQOARHGZjkxwlzEiQURIjYk5MMpU+KaTTvmCBxmDs1HT/s9CkfjD2corZI23zYUdWjp4G2ngsAFA7+xr4Kx4nxp+ANrTUcgdV+xGUNVz0WqwOVjebUaURJSp6F7hZRAewC2XBPzuPDHT7ML+lWtESU=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1686848128; cv=none; b=LmFmyXzzrmnjZbUn8Nt5Ez2j8zDiUvMZxmo8J7sFTslblJOY+hNff2amljrSzH9+eKfsMJW4sYuWk8zmlwgX5TWIZgpaEu3cdeFl3OtGyYNzSBWnzGVUI3+VJqH0XPNjnVp16aweDl9mB8PYduC34OHlad944+HxXDsB2fPARJJgXl5s0SwxcVSdLNTdaCGz8mRdhaiJa4Anz64kf+F6egsNJrwUlkv/marJ4pr4ohpb0yy/ZI35/NXg6waVoqxphtBTIjQBTd6IE7fahj8VLMvEYL6kuUMCo+gEAOJqM3esFuLm5ZUCql5gtJMzuDE3OXis/fEK39DHq2Es5UfoMLlJyMCtJFP6Z6FZuqXK67MH9/h2Nqhbgz34MUzdtqY5XyKO551NbgwVu7Vz+dwaNTTuk+Ib60W6KpIAholcEbb8Jl4hfXOU5aivHyTww9cTkLsqudPkpporCpO/ih6rJ4F/pqORCU8/l/0oNBRLolRgTsPSOEDDvgZ9C3RZ85NDFHsSzRuo9EPJCcE81XqWhVOVHuYlxpP+fnm1V8ESEzbeP5Q+4gkFnnP4vlVUu/VNXkYV9/x06o+UC00Qka4JGa/+1K1PXLlFzfUBk4NVeEMyxj/xLifavbf7zEDy1xolGIc4ckEt9pR2LBzl9v3l77zHOfldG4Q7DnPbgUWqODE=
- Authentication-results: smail; arc=none
- Delivery-date: Thu, 15 Jun 2023 19:00:19 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1686848128; bh=gwdenKjQOa5bozDt4yaVaQndyEtW9T+Hx1MMmZzpN4o=; h=Date:From:To:Subject:References:In-Reply-To:From; b=fCY1uUmHg35D7MK6Tvqg6TMNu+Ds2wslxK0Z0euECy4m49T87xAcqqAbpdwXtRrlZ ixShoraU+/bmAoeOIxNvYzmFZL5Qjf7QLeF4TD60Z9z0LPmH54zOMoc2ZMLzwAOfOQ dRXKMYCYkxrWWBJDwfaVDPEEhB2Ko59We9qy8UtA0mGTvm0iYCACu1vnH4BhCmJViC G258K75kbILI+jWReyHm1kx58H08VwVd/cqU/SLs3gyRPTJuMCKgrUktjgC4qrSJBi wa2aKuv2PO8d9jlO0kcZrqzXWkvwyI3hso/EsNS7DjJQtSkHUfZ6itaswWGzF3oQ32 vWk/bKK1v8t17yMNnAHOvQkw5PXw1XKEL8iDqBxGEKWQYSEqs6GPc2Bwfs3T9BeaC0 39kQQAmTvg3ffVcr9KMXNnYJ/ahPQkkeTd+HSDJZwzA78649ecdYaK8o0tIwQ+FT09 KGMcqdlc1DIS/nlT7Pq88WSPFYNpQU85Ayma38CYokl2bSOvYQbops2ceW4c98/OLg eCj1ScV9E5UPtj7BAYqrasASzJFIu9PNCxOvJiv/2rrfYqZ/V6x+EGcvSIIpZt0gLc c1HBKO+dI51bOZATDZk1sIlkBRQsuiS1WQZhmPouW2J24ZkvD+vvP67DpKm+aN2MbQ 3Iqsldb21xSW6bm1L1xnSj9E=
- In-reply-to: <74ba030b81f3f63d30f6a344c05ad4c3@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <a75d9672c5e120ae0299dd22da4a273a@stamm-wilbrandt.de> <74ba030b81f3f63d30f6a344c05ad4c3@stamm-wilbrandt.de>
On Mon, Jun 12, 2023 at 03:08:46PM +0200, hermann@stamm-wilbrandt.de wrote:
> Any thoughts on speeding up "powm()" or "Mod(sqnr^(p/4), p)"?
> Or another way to compute sqrtm1 other than slower "lift(sqrt(Mod(-1, p)))"
> to compute sqrt1,
With best known algorithms, compute square roots is fundamentally harder than computing
halfgcd. halfgcd can be done for the cost O(n*log(n)^2) while sqrt cost is O(n^2*log(n))
for a n-bit prime.
That means this is n/(c*log(n)) time harder for some constant c.
Note that with best algorithm, ggcd can also be done in O(n*log(n)^2) but it should still
be about 3 time slower than halfgcd.
> or even slower "qfbcornacchia(1, p)"
It is easy to fix qfbcornacchia, it just need to use the right formula for the
square root...
Cheers,
Bill