Tim Peters <t...@python.org> added the comment:

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.

----------

_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue37863>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

Reply via email to