Mark Dickinson <> added the comment:

> 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.


Python tracker <>
Python-bugs-list mailing list

Reply via email to