This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients mark.dickinson, rhettinger, tim.peters
Date 2019-08-18.22:22:47
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1566166967.45.0.868814849661.issue37863@roundup.psfhosted.org>
In-reply-to
Content
For posterity:

    "Modular Inverse Algorithms Without Multiplications for Cryptographic Applications"
    Laszlo Hars
    https://link.springer.com/article/10.1155/ES/2006/32192

"""
On the considered computational platforms for operand lengths used in cryptography, the fastest presented modular inverse algorithms need about twice the time of modular multiplications, or
even less.
"""

Lars considered a great many algorithm variations, and wrote up about ten of the best.  Several things surprised me here.  Most surprising:  under some realistic assumptions, _the_ best turned out to be a relatively simple variation of Euclid extended GCD.  Nutshell:  during a step, let the difference between the bit lengths of the then-current numerator and denominator be `f`.  Then look at a few leading bits to pick whichever of `s` in {f-1, f, f+1} will clear the largest handful of leading bits in `numerator - (denominator << s)` (this test is meant to be fast, not exact - it's a refinement of an easier variant that just picks s=f).  The "quotient" in this step is then 2**s, and the rest is shifting and adding/subtracting.  No division or multiplication is needed.

This has a larger expected iteration count than some other methods, but, like regular old Euclid GCD, needs relatively little code per iteration.
History
Date User Action Args
2019-08-18 22:22:47tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson
2019-08-18 22:22:47tim.peterssetmessageid: <1566166967.45.0.868814849661.issue37863@roundup.psfhosted.org>
2019-08-18 22:22:47tim.peterslinkissue37863 messages
2019-08-18 22:22:47tim.peterscreate