How do I find the lowest $n$ for which $a^n \equiv 1 \pmod{b}$?

If $\rm\: gcd(a,10)=1\:$ then order of $\rm\: a\:$ in $\:\mathbb Z/1000 \:$ must be a divisor of $100 = \lambda(1000)$. You can compute the order simply and quickly by computing in order $\rm a^2, a^4, a^5, a^{10}, a^{20}, a^{25}, a^{50}\:$ by squaring or multiplying previous entries. This requires at most 5 squaring and 2 multiplication operations $\rm (mod\ 1000)$. Obviously the same sort of optimized divisor lattice searching works for any modulus.

Alternatively we can use the following well-known simple order algorithm for groups - which is based upon the order test.
This thesis is a good reference on order algorithms in generic groups. Here's the abstract:

As I discuss in my answer to this question, this is a hard quantity to compute in general. For practical purposes you should use exponentiation by squaring to test the possibilities (and you should definitely use exponentiation by squaring for computing remainders in general; this is how computer algebra systems do it). Note that using Carmichael's theorem is not trivial, as it requires that you know the prime factorization of $b$.