pycryptodome
pycryptodome copied to clipboard
Legrandin
Improve speed of GCD, size, inverse
Apply the following optimisations that use builtin C code where available: Since Python 2.7 (i.e. always), the length of an integer can be computed with .bit_length() Since Python 3.8, the inverse of a mod b can be computed with pow(a, -1, b) Since Python 3.5, there is a gcd operation in the math module
Strange. The errors are all on python 2.6. I thought this wasn't supported anymore. Anyway, I'll make a fix to make it work even if bit_length is not available.
In that case, it is better to pull 001eb877c3e615804fe41cb59120d367ee65ef29 instead of 249ce5540caa080abf381a6c7839274980ccd8a9, saving seven lines of code and a try block :-).
if speed's the reason, shouldn't the code rather define different methods, so that the exceptions aren't thrown and caught every time the functions are called, but only once, during module load?
Good point. I went for readability, and the fact that this solution already does 95% of the gain that you could get. But indeed, a load time check would give you a few percent speedup. I should have a look at exactly where these routines are called to see if it is worth the extra effort.
Let's see if this works. If it does, we'll get incredible speed for size and GCD as they contain no Python code whatsoever :-)
Sorry, I meant checking for negative numbers before calling .bit_length() would really slow the code down.
Almost all changes are merged so I close it. Still keeping the test for negative number when counting bits.