➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author lschoe
Recipients lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date 2019-02-19.16:32:05
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1550593925.9.0.734386966568.issue36027@roundup.psfhosted.org>
In-reply-to
Content 
> ... to see `pow(a, p-2, p)` beat a pure Python xgcd for computing the inverse.

OK, I'm indeed assuming that modinv() is implemented efficiently, in CPython, like pow() is. Then, it should be considerably faster, maybe like this:

>>> timeit.timeit("gmpy2.invert(1023,p)", "import gmpy2; p=2**61-1")
0.18928535383349754
>>> timeit.timeit("gmpy2.invert(1023,p)", "import gmpy2; p=2**127-1")
0.290736872836419
>>> timeit.timeit("gmpy2.invert(1023,p)", "import gmpy2; p=2**521-1")
0.33174844290715555
>>> timeit.timeit("gmpy2.powmod(1023,p-2,p)", "import gmpy2; p=2**61-1")
0.8771009990597349
>>> timeit.timeit("gmpy2.powmod(1023,p-2,p)", "import gmpy2; p=2**127-1")
3.460449585430979
>>> timeit.timeit("gmpy2.powmod(1023,p-2,p)", "import gmpy2; p=2**521-1")
84.38728888797652
History
Date User Action Args
2019-02-19 16:32:05lschoesetrecipients: + lschoe, tim.peters, rhettinger, mark.dickinson, steven.daprano, skrah, pablogsal
2019-02-19 16:32:05lschoesetmessageid: <1550593925.9.0.734386966568.issue36027@roundup.psfhosted.org>
2019-02-19 16:32:05lschoelinkissue36027 messages
2019-02-19 16:32:05lschoecreate