2
$\begingroup$

Let $I(a,b,m)$ be the smallest postive integer solution $x$ to the modular equation $$ax\equiv b\mod m.$$ What is the quickest way to find $I(a,b,m)$ for given integers $a,b,m$?

I know how to find it with the generalized euclidean algorithm, but is that the quickest way? Also, are there any curious properties of $I(a,b,m)$ like efficient bounds or identities?

  • 0
    I would be surprised if there were anything more efficient than Euclid, unless you have restrictions on $a, b, m$.2012-12-31
  • 0
    You might want to review, if you hadn't already, [**Method of least absolute remainders**](http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations) and also review [**Algorithm Efficiency Comparison**](http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency). You might also want to review [**HAC - Section 14.4**](http://cacr.uwaterloo.ca/hac/about/chap14.pdf). Regards2012-12-31

1 Answers 1