We now have a working version of the Extended Lehmer GCD. The implementation is currently not in uniform time, but I know how to adapt it so that it is. I also finally figured out how to get the binary GCD to run in uniform time, so I plan on trying to implement it soon. We will soon see which is faster/more uniform. In any case the bottle-neck preventing us from moving forward with modular inverse, Montgomery reduction, and modular exponentiation is now gone.
We now have a working version of the Extended Lehmer GCD. The implementation is currently not in uniform time, but I know how to adapt it so that it is. I also finally figured out how to get the binary GCD to run in uniform time, so I plan on trying to implement it soon. We will soon see which is faster/more uniform. In any case the bottle-neck preventing us from moving forward with modular inverse, Montgomery reduction, and modular exponentiation is now gone.