0
$\begingroup$

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)$?

|improve this question
$\endgroup$
  • $\begingroup$ are you looking for calculate $\text{GCD}(a, b)$ in Montgomery? that is $\text{GCD}(aR^{-1}, bR^{-1}) \bmod N$ $\endgroup$ – kelalaka Sep 28 at 9:38
  • $\begingroup$ @kelalaka I'm looking for non-trivial agorithms for $(a,N)$. Non-trivial for me means that they are based on Montgomery arithmetic. $\endgroup$ – Alexey Ustinov Sep 28 at 11:00
  • $\begingroup$ Binary GCD/Stein's algorithm can be interpreted as using Montgomery arithmetic. $\endgroup$ – j.p. Sep 28 at 11:31
  • $\begingroup$ @j.p. Sorry, I don't understand your remark. Did you mean that both of them use division by 2? $\endgroup$ – Alexey Ustinov Sep 28 at 12:33
  • $\begingroup$ @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$. $\endgroup$ – Alexey Ustinov Nov 1 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.