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.
My question is about
greatest common divisors with N
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)$?