Author tim.peters
Recipients mark.dickinson, rhettinger, tim.peters
Date 2019-08-15.17:37:48
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1565890669.1.0.859298443389.issue37863@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2019-08-15 17:37:49tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson
2019-08-15 17:37:49tim.peterssetmessageid: <1565890669.1.0.859298443389.issue37863@roundup.psfhosted.org>
2019-08-15 17:37:49tim.peterslinkissue37863 messages
2019-08-15 17:37:48tim.peterscreate