Looking for clarity on this modular inverse code

So, this is taken directly from VanitySearch. Check it out on GitHub. It’s from a different project, but the source file is the same. The _ModInv function is for calculating the modular inverse using the extended Euclidean algorithm, which you can read about on Wikipedia. It works with signed 320-bit integers, likely to handle any overflow or underflow issues, but that's not what I'm stuck on. I get the basic Euclidean division and the Bezout coefficients, but where I’m lost is how this specific implementation uses 63-bit shifts. U and V are filled with the values of P and R. Basically, R times the return value gives 1 mod P. But after that, I'm confused. Can anyone help me understand this better or suggest a site where I can find folks knowledgeable about this kind of function?

This is Extended Binary GCD Binary GCD: https://xlinux.nist.gov/dads/HTML/binaryGCD.html http://www.cut-the-knot.org/blue/binary.shtml Extended Binary GCD explanation with lots of words: https://github.com/DavidNorman/gcd

Perfect. Now I'm going to try to figure out how the binary extended GCD operates with many words - this has been a pain point for me. I'll get back to you later.

I mean lots of words explaining it. Here is the code I made back in 2019, this is slower than the 5x52 version (it is 8x32), but was faster than xp-2.

OK, so now, finally I got the hang of this! The key to understanding this implementation which is not a conventional binary egcd, is that this implementation is DRS62 (delayed right shift 62 bits) - actually it says so in the comments even. Basically, the reason why it's called such is because it implements the optimizations in this algorithm: https://github.com/pornin/bingcd/blob/main/doc/bingcd.pdf This paper describes how to optimize EGCD when you are working in a modular field with fixed-size registers, like 64-bit registers and the like. Although in the conventional binary gcd, we are left shifting (dividing) stuff by 2, in this implementation we are actually multiplying some of the words by 2 and then we "fix" it by dividing (right shift) by a bunch of twos at once - 62 times, to be exact. Those lines that have MM64 and MSK62 on them followed by multiplication, addition and a right shift - that is Montgomery Reduction and that basically calculates the modulus by P. It uses some fancy modulo 2^62 stuff, but I will have more to say when I write a separate post about this. Much thanks @j2002ba2!