Message335956
> it's still a bit subtle that you have to use pow(a, -1,p) instead of pow(a, p-2, p) to let the modular inverse be computed efficiently
That's not 100% clear: the binary powering algorithm used to compute `pow(a, p-2, p)` is fairly efficient; the extended gcd algorithm used to compute the inverse may or may not end up being comparable. I certainly wouldn't be surprised to see `pow(a, p-2, p)` beat a pure Python xgcd for computing the inverse. |
|
Date |
User |
Action |
Args |
2019-02-19 15:32:02 | mark.dickinson | set | recipients:
+ mark.dickinson, tim.peters, rhettinger, steven.daprano, skrah, pablogsal, lschoe |
2019-02-19 15:32:02 | mark.dickinson | set | messageid: <1550590322.49.0.739872280444.issue36027@roundup.psfhosted.org> |
2019-02-19 15:32:02 | mark.dickinson | link | issue36027 messages |
2019-02-19 15:32:02 | mark.dickinson | create | |
|