|
Bill Allombert on Sat, 15 Jul 2023 11:13:20 +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: Sat, 15 Jul 2023 11:08:39 +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=1689412109; c=relaxed/relaxed; bh=GrKx5IubhrjowfAnMCe1ASmwh7mVd8kysFbc57Rl4ck=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=zsgXI7oRr3GShGeWEnxu0X72XC+PJFA99baCJZrzeRmcgR7eqt2B7gvEt35ZutRXcG+CmjoZwSRk7QTtWl2PQzr9pRNkpKAQwXERQS2yDz3wCUPBPvjHDQblXMBRDI00NKLT79RfjRKo5qFvWzwf3gkiaNDMUg17Fu+FwMwOH0/JQ6Jru7EINHj6FmJeQnWnEJuCuMS8ns0l/JDfDPlRuNIorD9uu//NNLD7eoyRvmKGWhMPA+e1OD2qXkY9o+lpK2TqEPWS+AJ11BlwO2pRAypDvE6hC6ImzSYpfRqLvbWifxWcyeYhdHfGEt0yVPIMmEr2oxTSbO+Cvc/iHfmLOVXcZdRH8UVB8zYIfBzcv32nAG3RvauKZ9lSMo6vPMFPdSEfqQmFsY0HRW8vbbnvrLM4+W6PzD70n+KXBFSS6lLIHfqUrLQ9WPaRaEJSfuX97P+cOkAOSYMSCCD/Z0v53QkVLuhs4lxDCszrclFFKlU+6u8ug3jNeqTEQ9YZldmNoz+V/4Fs9bNmEVNp5kO4G9qQNs4x0nEKAPKJEYAsDO+JZqwTCt4ODvc2g+nd2vnXIctDqVaLi+Rp8CMktgbbiFKNU45TPYVmQYcB5IftNeCzT2bRZ0YiwClH5vjC8ohvqP7RnWzQWMRxKgccVMnbqBZN2lpxrr/tyAzvKBE8L+0=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1689412109; cv=none; b=fpWzYbea30p2Qux8Z3oFGD9atJRU5LttbQE4U8cFy4HZjqfGwcag/EClowg1BthsuvnOQ5H1598OH4PODp0EzQR2JSL8z6ZbguIl8RpLMKF/jN9tRxrG4nHXTilGHOWcGc5Re5eZidxjuyJLdiXDz7iBwO7E9jP8gbpx/BoRLOKxSwc3rUcQXcnYBpTULMNp10TgbQVDkIG8IldqUBWUQE1Rb8u1B5AM4ZQBZD9wt3+r/FPl4Ludcg4scOJ8Q1mUtuMA1aeMn49sSohr855kuyceTdi+3XZecxmKOnkANDA3EE9ZMqSsMMSFZSzKWK+mInL2gU7KoN0Q9gqf2GDMfK+VRtvimcHjn/PyIjbcbMlTPC+sstCdM2nN8LSnr93vg2z/dTVOorQW1JIfI1dOmGpgQt1R+AjSHztIuoB04us8/mIB8QG7IxFJvXWYJHObzbwgN2XFK19+yMQJGZ1oe2rjA+l/pDzLj+7bWVlZXdVYjBux43NvJwpkKeTpFmFAn7F17l8DPHv/iHBi6cdbumpQSvUlH44+gzq2YA0Za9uSjqLjzwA9qYKa1vbhwHaNKM9PTuanJPJCBB9FyUUEWDpcZA2pPU9WMIjUoR+lcnc2W+urBaPkj5LhUmJNiF6Nek+AKKN7Hy8sn/aItqwNNke96DavwRhZDKbbq+DWv3g=
- Authentication-results: smail; arc=none
- Delivery-date: Sat, 15 Jul 2023 11:13:20 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1689412109; bh=GrKx5IubhrjowfAnMCe1ASmwh7mVd8kysFbc57Rl4ck=; h=Date:From:To:Subject:References:In-Reply-To:From; b=QEuEk3IBPlS8DoxHLIc8STunPvw3KQ0/sEd7aNYGRjt88PkJqo/wj8ydgdVT9jzs/ V2TXJzBM1YG1ecFvzq4KbpD3edZiJukFN0NUyP2OnCbkr3hhycxRvm5LJdj0mUdFbq zATVQPe6Dga3onNCI3Hn28p4ITlbIIkJipPkVrDUuIWRB7VTPcgo9wjfyK5oab1bA+ 9ViTHkpcNcnND7354aWcPN0ofnxZGb503nkI//XMwoqpiQl3mdEANPAOYmmtc3kjWp +gLadAqqFbwozlT/J48TySz92KLZA5rR2a5xGMQUchiDfy0sQLyw3tS8GU5+ljWS2L s/gFzli7GA2b7sKeAFntYtFu08wTQebk2RLyIjxuNNExpMZxhA0NAOYKjfBpZoPjUv 0v5RKmxkgrIDDBO+wxmwIGYyAH2Qxc6Rr/4rcur2FGBrbFc3g/8a9uRtzNLV7of4L2 t6XDFghxVkmM4WY/xZ3j3AQT7TBhKJc5KurgIUHitiRZNeFq7BKFBLXjK4Fib/pcVY 1hIwur6b6BZqoRtT8E4Eu2wSIgj7leqbO3JrqevYscIcaU7S8xrutZt6b0cDsVb4/J QDxmpkHmwx4W/LNid1EvL0j/AGXT/hp4JDoTimzVJLsH0rtHh18UqC6NIqfGJef3HU xOG4/5iwZBClI4e8uWGLdmkE=
- In-reply-to: <2007b5abf504136ac7374d3882f83c78@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <43475cd077e10ac2cebf5d8fb59c9118@stamm-wilbrandt.de> <ZJV+RwzesyTLJTDj@seventeen> <ZLGCSwm4nqalbZOe@seventeen> <6fa2e06c0ed114049cd6a46a43d7de34@stamm-wilbrandt.de> <ZLHKCfbl6PBsmD71@seventeen> <2007b5abf504136ac7374d3882f83c78@stamm-wilbrandt.de>
On Sat, Jul 15, 2023 at 01:05:08AM +0200, hermann@stamm-wilbrandt.de wrote:
> Since Pari/GP user guide proposes in section 1.2 to use gmp kernel, you
> might want to upstream your base 2 powm() enhancements to gmplib?
Sure, but for some other prime numbers, it seems to be slower than GMP,
hence my enquiry.
For example, could you try
p=fibonacci(148091); Mod(2,p)^((p-1)/4)
and
p=fibonacci(148091); Mod(3,p)^((p-1)/4)
but more importantly, we do not do anything clever.
So I suspect the bit pattern of the exponent to be relevant.
Cheers,
Bill
- References:
- 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>
- Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- From: hermann@stamm-wilbrandt.de
- 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>
- Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- From: hermann@stamm-wilbrandt.de
- Prev by Date:
Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- Next by Date:
Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- Previous by thread:
Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- Next by thread:
Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?
- Index(es):