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
