Message349811
Why I expected a major speedup from this: the binary exponentiation routine (for "reasonably small" exponents) does 30 * ceiling(exponent.bit_length() / 30) multiply-and-reduces, plus another for each bit set in the exponent. That's a major difference between exponents of bit lengths 61 ((P-2).bit_length()) and 1 ((1).bit_length()). Indeed, I bet it would pay in `long_pow()` to add another test, under the `if (Py_SIZE(b) < 0)` branch, to skip the exponentiation part entirely when b is -1. `long_invmod()` would be the end of it then. Because I expect using an exponent of -1 for modular inverse will be overwhelmingly more common than using any other negative exponent with a modulus. |
|
Date |
User |
Action |
Args |
2019-08-15 17:37:49 | tim.peters | set | recipients:
+ tim.peters, rhettinger, mark.dickinson |
2019-08-15 17:37:49 | tim.peters | set | messageid: <1565890669.1.0.859298443389.issue37863@roundup.psfhosted.org> |
2019-08-15 17:37:49 | tim.peters | link | issue37863 messages |
2019-08-15 17:37:48 | tim.peters | create | |
|