Berry Schoenmakers <l.a.m.schoenmak...@tue.nl> added the comment:
> ... 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
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue36027>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
