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
    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

2

Euclid is pretty quick, and I don't know a quicker way.

  • 2
    When I was a freshman I invented a search algorithm, which is a general problem solving algorithm. It works in $O(1)$ but it has a rather high failure rate. It's called **Lazy Search** (or in the general case, **Lazy Solve**). Pick a random possible value, if it's the correct one return it; otherwise go and have a beer. I think this is a quicker algorithm than Euclid's!2012-12-31