Author tim.peters
Recipients mark.dickinson, rhettinger, tim.peters
Date 2019-08-15.23:57:56
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1565913477.09.0.712187957974.issue37863@roundup.psfhosted.org>
In-reply-to
Content
Mark, I did just a little browsing on this.  It seems it's well known that egcd beats straightforward exponentiation for this purpose in arbitrary precision contexts, for reasons already sketched (egcd needs narrower arithmetic from the start, benefits from the division narrowing on each iteration, and since the quotient on each iteration usually fits in a single "digit" the multiplication by the quotient goes fast too).

But gonzo implementations switch back to exponentiation, using fancier primitives like Montgomery multiplication.

As usual, I'm not keen on bloating the code for "state of the art" giant int algorithms, but suit yourself!  The focus in this PR is dead simple spelling changes with relatively massive payoffs.
History
Date User Action Args
2019-08-15 23:57:57tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson
2019-08-15 23:57:57tim.peterssetmessageid: <1565913477.09.0.712187957974.issue37863@roundup.psfhosted.org>
2019-08-15 23:57:57tim.peterslinkissue37863 messages
2019-08-15 23:57:56tim.peterscreate