Re: Finding minimum in arithmetic series modulo N

On Thu, 10 Apr 2008 15:33:03 -0700, 3130 wrote:
Consider the sequence of values generated by:

x(k) = (A + kD) mod N

where A, D and N are positive non-zero integers, and k takes values 0,
1, 2 ... M-1.

Other then brute force search, is there is a way to determine the
minimum value for x(k) and the value of k for which that minimum value
occurs.
[...]

Here's an idea to consider; still a brute force search, but
with a good chance of terminating much earlier than when
just stepping k=1,2,3... -- Suppose gcd(D,N) = 1. From
Euclid's algorithm, let a,b be such that 1 = aD+bN, so that
aD == 1 mod N. Let i be the smallest integer such that
0 < -a + iN < N. (i exists since (D,N) = 1.)
Let c = -a+iN and k = Ac mod N. (Now A + kD == 0 mod N.)
Until k is in range, set k to k+a mod N.
Afterward, compute min = A+kD modulo N.
(I haven't figured out how to adapt this if gcd(D,N) > 1.)

-jiw
.