|
Bill Allombert on Fri, 23 Jun 2023 13:18:18 +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, 23 Jun 2023 13:13: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=1687518782; c=relaxed/relaxed; bh=O5oULBT8AxU+48Tuj8D/5e29Tyuo1uJHVWFLn8uoCzE=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=SC8ara8YlGalbHNj5ZJ/TwitlSre/QINFKMlxWFuss25Z6CyI/a/3yolysVYogyYJ6BZg5rCuw8Oxq2/SYAAsJa9rA2cdPbFU2R0lwbf3BJMEKKIwbaBhTcRE/NtmIH2CIuK5bbbfTjHZB/+5yIBWoqfPW0Vc0tYlsi8wUux1zgFxqDCkLu2YR643uAG/eIYChIOjoTEG3ByrCLvjju6arCmENylAbbScjhEp57SNqu+6L1pHADchQzIuGh1P3UBWS/3yYGeLruL9bqG6ZOZ+94RWXc4JlBLcm4WDc8kMyPh6g+IiaboO3BskXbuugJqj/msdcm1qGCpGuAPYGRwH6eIidFIsSTIYDdqBFRJHpi1vDs0O+SKaT3RlsEFGJPjzZ4ah+GNEUpXnQgOdud1gXQQXOKDlNdSut5XCwXbRMimrN1EQn93INI885INoc7YIal8gPYCu44eblyLoGAHXzBk+vVFm3lTh8GpZ9QEdV4DZ/AgGqf0XIHJEzqRxV3O15Qm7EjFUt95pLW0HM2xzLnB7+srOosQ+dOrYTfo9LMfavNgS/nQBmoG59+pXdQHXD7SsbI/IF0w8jKt41YWtMPqwJvVomGRvmTn7oA3dDu5mswfxgGCG1ikb5zd6xSCe0H1+DP8TEMXRUpepzS6UsSVShFp4CsT4Tjdydk45j8=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1687518782; cv=none; b=rOM0LZskuKmT+V5GnMDU/9k0Px3QCVTULOTdNvlR9SBwqFtTktdtie71/aJgQ+YXKH1ufKCIRVkyxrhMMzf8TsjjqbaZvFjXFtxreiYMv+xbzKrtnQoG2sZqjBuSnFAFPZkZWD0bD54O1slx8jUe36H+3QxVRXng39l6oWimm7SLVpdMYp2lDtFvBqhmqj3xoqi3wxO5M6IkUu1N3IJ7HQHWRRuCxS3Oa2A4GXV7xVoWHYz/Cz0A8IyyRj+L4KGj57CedYJiyY/wxqcCjdE79va1/d0VU/WgMpmqigAymd2Mx0nM1KBxwG/F++kFDHx1MtbQSQEFViNLMHmAyo2kT5R4jx0tOW3Fay6EBuaXwOeuoV5OIkOahNNfxuqQswZdZ5A23j1wGs/5+8CS0JQlbDUAHRmxj+wqOjl061E+6xNEqPEI7UJni5w5l4QDw1HA1ih2xacefivRCtNP6fVcu1klIZiuuYWvsdhHc71kWO1hrRhFTxR3cepP7MtDiKa2Mk9wVhuAXIwt+AkeUSy1AcB2209OXNUAN0AiebdoK2gGVqsBe/vYTSV2u5Af1nSp+bn2M30h0UK5Qy63PBH9/+SKvVQKHUUk6f+q5YguagoP+iV76yxunE0iNuVEGqie7bL3cvvBUUu1Pev440KpWkfet2JjTg4qqNx4fE/mkGM=
- Authentication-results: smail; arc=none
- Delivery-date: Fri, 23 Jun 2023 13:18:18 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1687518782; bh=O5oULBT8AxU+48Tuj8D/5e29Tyuo1uJHVWFLn8uoCzE=; h=Date:From:To:Subject:References:In-Reply-To:From; b=DO+AX7g5iO0VqICc4m1eU5dK5Ss8Q2uDXLticz2xWStAqrLWHItiiIZS+m6zsPaMU 1WtBg0mCTUd+rkINdj1T1jMMVcbUMZ2IYUeMP0EM4Pput9yCeSXIim9DXyXRtxoIzZ /ENgLg8oXvskuvObMzQopVDA6r+Qs3PwqsR+beZi0jaTlt/ZI2gtLzSMEARtFZL2J3 FcW5PNOG2zXGVNfCfcmgX+qgeqy5/4C0uBo0m4fp/2X1/bU096STaM5kEb7d7g/ma7 scEDiNdSkmkjsya5F5gFVTb5dnmpj/mFEoasARpDjvh86x5ukOml3Pd0ycOUvCAhiQ rNEe0rq6MU5x5F1oq3O75gLy8n73P9ByD4v2csVYiqYqK6waRHw3PPOKPoeuZ6sEd8 Q94zdw5D3MkqbFqsKSQTJSsBcAsJHoQ5WCq6B20DuO0ELKfZKnEsy9d3AfPirbpjAY 2cieawDMyg3gsRx6hgxsnp0N0h8IOUiUfFBAMWpZp+8EyGzrMK77u/cv7Jxm2IzAc3 0PYQGmVW6tXUu0aviyPqrQVosk+YyRR0u6rw5+won1I0QeD5WFzwfZp+SOFC5t59ms ULRKuvy3UXnug6ZX4zWrjoOhmIEBmFCZ5yKbiQHydhIBKEkPyxtwx3wvBFlCW0tSx3 sdx6zjd0LYFu+vaIf1yaQIhM=
- In-reply-to: <43475cd077e10ac2cebf5d8fb59c9118@stamm-wilbrandt.de>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <43475cd077e10ac2cebf5d8fb59c9118@stamm-wilbrandt.de>
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.
Cheers,
Bill.