|
Bill Allombert on Fri, 14 Jul 2023 19:18:30 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Fri, 14 Jul 2023 19:13:47 +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=1689354818; c=relaxed/relaxed; bh=sy3uv1Vjd7HWDZhqovLTUk13wcNwSAP+84ufKwY+SQA=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=ZQhlLJFhzx6wVjGrj4X7AQZldRpWGFMH8kD8Q05VvzsYzH+k5LixfBHbM0i0fu3UQ7wAGS6aoBuPEX9u1brKDOW72AdtKSj19aCiqkKtoJlXE8472kMlgSPQ6XPiSSvLTDEVLV6MhRgMWGjVxityX/suDiHhno7ByfYuHQi177/ZhPeInm3k7B1Rnj0nsizy/01uOvDTbcVKix6pbACHXAVBXp3nzegJNWlkTT17rXyjoHJSgE7hFKIUMPjHMmixQWgVYqhiU0aGPe32fJWEnPmqC5Hu9QykLwHE2r/nPIMqIJkUxZaMsNTuT2Q+zCPhI5O8jaCNInXKxEG/Soi9XRCqQcDQP6/g/7+LB/cAyA4V0vCbLFEuHY1cm8AnjR8A0au52F4hGqogH2bUDo8uQB/yC+skuXQhhiwartv/Dq5BT4hXNoRnhKUY4F8iSZ7iYgR4RIC+mvz02oLx+nynnwvUpqXAQvFYHCgEdQM6L9b9BqgZMil2L3dKiuj3VlPekFyZn5GzEGlwHeTmPTR9AZ5Kbodxf4hElchArjPQ58q+/S6XS33hUth5GTfIInCNe8gXuryMbxgScEFmb3VADNJalH1ceIKcjlwoZHEgkga8SpKcbIhOf8r0HQqYtQg/Ker4OmfbQAmLfbWBw6Rl1YdH1eEc4trYHdNM9atOrls=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1689354818; cv=none; b=U/aAKhcodHVTbgqyr1COqeX8gRRWKLryFZU3/g0+8rLFeOYIL7u/eqJlRHg4a13YsqueDCIjPQVu2Uvha3ad3W9VFgB2nSzZJbE62R3NwytlsixXICvw3O2/ObVjV0fbar3J6Vkk8bvMCxpvO7TwTybEzjy1oebOeGuzlOrupFuNSdO/JREXEyZNdPaRzx30rhCn7tP8kajwqTZwdyopOJcFuY0uqy+6KcytJKQXQDPcWtCl3wOEz1vopUbHBRZWtm+D57zw0CyzEYPhcZxIf/vW/Sg55zmwqSi32wKr/J9ck8u9yHLpWEJWWfUMbMhF8MFj8kfX4hmQIK8tgpUHliUf31o6A2AiP7DtoqLOD/ZcPYIrxnV14OWhTwJF6io+/mv94iXQWKMgXKf+48XKcYw7NcX7XK4in+qX0s8c0yZtVmyzBnb7JoBYi3W4ZpsSgOzFUrn+A0BiyTj0uaP6T2EoOR+HQKgwQT1rWejgfBW5LVOscdya+XXcCsGmL6fg5C7/WpbkIfqP9sVr+lRCIt6wj8kZM+2mHyquyvYlnmroeVc1BBl/fT0b+lY/AM9/+jEgXzMsjfZdd4v15dqToJMZiAZxv6l2jT2511zX5Rxl+WNtKw+2nINgydrU3JoN9zW6qzMP896OO7jZ8ncmxXdbibRVcO4eo0qPsveY74U=
- Authentication-results: smail; arc=none
- Delivery-date: Fri, 14 Jul 2023 19:18:30 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1689354818; bh=sy3uv1Vjd7HWDZhqovLTUk13wcNwSAP+84ufKwY+SQA=; h=Date:From:To:Subject:References:In-Reply-To:From; b=a7BwK6TugZ0A3yKhCdzCeWt9wdWu8m90HX74Atga9s5KJdZjAg/hh2HrVmjw5pvt0 MqCW7dZr1mZAm0vE9C0FpbomX/t+H8JZe2900TQpqLfikfbG8Kx0NUMy6Efrwt3H8l Ie3y8xAzkiFKDMvVtRQqag2y/OBDgReIY2ZEMjm/YkgHbcvUvuyU5WjizXP3d8yq9E RHGwzxvVltnVTBRD/0I4yLtP0BXO/eZ/75yauE4Vz2YbVTlnDgrBB4yHbMEQCW61xu UeFe+Xy2vLreutGqLXbg9MP2021dpbqCdbhebtvNF3OJM+v20x0nRUYDdAMu8aDOeH o/LGCotq32yT0bVeiJC6D8GECeXBF8rQUfzMcgYHJ0vKbEHwRcppkLp753K4ozxw7D jOKQTaPi7YagOqq4W3j1xfKX2v0xCGdvloGmNEVZEGaLzczPSpqiRKvR06CwkUmPu3 zh1BtklWQH7XWjzZGBmcIxDPxa3FC6x1ANOueAWPmTMlJFYmMD4uFIaIeD42f1V+ZC JLmqMe2rl46iJC7dKIhObFjrU30djjdjsx9aFgueKhOctg/qG6G4WHvyicsMu0BJ8r T8s5gQ3UrSyBYmh5EA2FKxzm7WfhlVKT7gy1lhEGFL0G+YyXkDfyP6wCxl+sEgsk7I +MReFaRoxNAuaMzL1wpLc63k=
- In-reply-to: <ZJV+RwzesyTLJTDj@seventeen>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <43475cd077e10ac2cebf5d8fb59c9118@stamm-wilbrandt.de> <ZJV+RwzesyTLJTDj@seventeen>
On Fri, Jun 23, 2023 at 01:13:11PM +0200, Bill Allombert wrote:
> On Fri, Jun 23, 2023 at 12:15:39PM +0200, hermann@stamm-wilbrandt.de wrote:
> > My Linux gp-2.15 runs with GMP kernel:
> >
> > So why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr,
> > n/4, n)" on same Intel CPU (running at boost frequency with single running
> > process both times)?
>
> The short answer is that the GNU MP library does not provide a function mpn_powm
> that PARI could use. mpz_powm use a lot of internal mpn functions for fast modular
> reduction which are very efficient but not public.
>
> Now, I could add a wrapper for mpz_powm for large entries but 16% slower is not
> that bad and we need fast modular reduction in more general setting.
Could you compare
p=(2^95369 + 1)/3; Mod(2,p)^((p-1)/5)
with mpz_powm and PARI ?
Cheers,
Bill.