Author mark.dickinson
Recipients mark.dickinson, rhettinger, tim.peters
Date 2019-08-15.18:32:07
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1565893927.28.0.803612838967.issue37863@roundup.psfhosted.org>
In-reply-to
Content
> That's a major difference between exponents of bit lengths 61 ((P-2).bit_length()) and 1 ((1).bit_length()).

Right, but that's stacked up against the cost of the extended Euclidean algorithm for computing the inverse. The extended gcd for computing the inverse of 1425089352415399815 (for example) modulo 2**61 - 1 takes 69 steps, each one of which involves a PyLong quotient-and-remainder division, a PyLong multiplication and a subtraction. So that's at least the same order of magnitude when it comes to number of operations.

I'd bet that a dedicated pure C square-and-multiply algorithm (with an addition chain specifically chosen for the target modulus, and with the multiplication and reduction specialised for the particular form of the modulus) would still be the fastest way to go here. I believe optimal addition chains for 2**31-3 are known, and it shouldn't be too hard to find something close-to-optimal (as opposed to proved optimal) for 2**61-3.
History
Date User Action Args
2019-08-15 18:32:07mark.dickinsonsetrecipients: + mark.dickinson, tim.peters, rhettinger
2019-08-15 18:32:07mark.dickinsonsetmessageid: <1565893927.28.0.803612838967.issue37863@roundup.psfhosted.org>
2019-08-15 18:32:07mark.dickinsonlinkissue37863 messages
2019-08-15 18:32:07mark.dickinsoncreate