# GCD in Montgomery arithmetic

Wikipedia article on Montgomery modular multiplication contains the following statement:

Many operations of interest modulo $$N$$ can be expressed equally well in Montgomery form. Addition, subtraction, negation, comparison for equality, multiplication by an integer not in Montgomery form, and greatest common divisors with $$N$$ may all be done with the standard algorithms.

It is clear that $$(a,N)=(\mathrm{Redc}(a),N)$$ since $$\mathrm{Redc}(a)=aR^{-1}\mod N$$ and $$(R,N)=1.$$ But the following thing is not clear.
Q: Are their any non-trivial algorithms based on Montgomery arithmetic which allow to find $$(a,N)$$?
• are you looking for calculate $\text{GCD}(a, b)$ in Montgomery? that is $\text{GCD}(aR^{-1}, bR^{-1}) \bmod N$ – kelalaka Sep 28 at 9:38
• @kelalaka I'm looking for non-trivial agorithms for $(a,N)$. Non-trivial for me means that they are based on Montgomery arithmetic. – Alexey Ustinov Sep 28 at 11:00
• @kelalaka Can you explain your formula $\text{GCD}(a,b)=\text{GCD}(aR^{-1}, bR^{-1}) \bmod N$? If $N=5$ and $R=8$ then $R^{-1}=2$. For $a=b=2$ we have $\text{GCD}(a,b)=2$ while $\text{GCD}(aR^{-1}, bR^{-1}) =\text{GCD}(aR^{-1}, bR^{-1}) \bmod N=4$. – Alexey Ustinov Nov 1 at 6:09