Understanding Modular Inverse in Code

Found this from VanitySearch It’s a code snippet for modular inverse using the extended Euclidean algorithm. Apparently it tackles overflow by using signed 320-bit integers. Not sure if that’s impacting anything here, tho. I’m good with Euclidean division but confused about the Bezout coefficient part.

Check out this Extended Binary GCD thing There are some decent resources out there. Like the NIST link and this one from cut-the-knot. They really get into the mechanics of it all.

Nice, I'm diving into this Gonna struggle with the extended GCD explanation for sure. Just so much info to sift through. I’ll report back later on my findings.

Yeah, it’s all about those explanations Here’s a piece of code I wrote back in 2019. Slower than the fancy 5x52 version but beats the xp-2. Gotta love these optimizations!

Got it all figured out now! This isn’t your typical binary EGCD. It’s DRS62, which is mentioned in the comments. It utilizes optimizations from a paper about modular fields and fixed-size registers. So much info to unpack but it’s making sense now.