Author mark.dickinson
Recipients lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date 2019-02-19.16:49:13
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
> Then, it should be considerably faster

Why would you expect that? Both algorithms involve a number of (bigint) operations that's proportional to log(p), so it's going to be down to the constants involved and the running times of the individual operations. Is there a clear reason for your expectation that the xgcd-based algorithm should be faster?

Remember that Python has a subquadratic multiplication (via Karatsuba), but its division algorithm has quadratic running time.
Date User Action Args
2019-02-19 16:49:13mark.dickinsonsetrecipients: + mark.dickinson, tim.peters, rhettinger, steven.daprano, skrah, pablogsal, lschoe
2019-02-19 16:49:13mark.dickinsonsetmessageid: <>
2019-02-19 16:49:13mark.dickinsonlinkissue36027 messages
2019-02-19 16:49:13mark.dickinsoncreate