multiplication chains that result in a constant modulo a power of 2

Question

Is there a practical algorithm that gives "multiplication chains"

To clarify, the goal is to produce a multiplication change of an arbitrary and exact length
Multiplication chains of length 1 are trivial.

A "multiplication chain" would be defined as 2 numbers, {start} and {multiplier}, used in code:

 Given a pointer to array of size [{count}]   // count is a parameter
 a = start;
 do 
 {
      a = a * multiplier;  // Really: a = (a * multiplier) MOD (power of 2
      *(pointer++) = a;   
 }
 while (a != {constant} )
 // Postcondition:  all {count} entries are filled.

I'd like to find a routine that takes three parameters
1. Power of 2
2. Stopping {constant}
3. {count} - Number of times the loop will iterate

The routine would return {start} and {multiplier}.

Ideally, a {Constant} value of 0 should be valid.

Trivial example:

power of 2 = 256  
stopping constant = 7
number of times for the loop = 1  
returns {7,1}

Nontrivial example:

power of 2 = 256  
stopping constant = 1
number of times for the loop = 49
returns {25, 19}

The maximum {count} for a given power of 2 can be fairly small.
For example, 2^4 (16) seems to be limited to a count of 4

Answer 1

Why wouldn't this satisfy the requirements?

start = constant;
multiplier = 1;

Update: I see now that the number of loops is one of the input parameters. It sounds like this problem is a special case of, or at least related to, the discrete logarithm problem.

Answer 2

You are asking for nontrivial solutions to the following modular equation:

s * m^N = C (mod 2^D)

where

• s is the starting constant
• m is the multiplier
• N is the number of iterations (given by the problem)
• C is the final constant (given by the problem)
• D is the exponent of the power of 2 (given by the problem)

Have a look at Euler's theorem in number theory.

For an arbitrary odd m (which is prime with 2^D), you have

m^phi(2^D) = 1 (mod 2^D)

thus

C * m^phi(2^D) = C (mod 2^D)

and finally

C * m^(phi(2^D)-N) * m^N = C (mod 2^D)

Take

s = C * m^(phi(2^D)-N)

and you're done. The Euler's phi function of a power of 2 is half that power of 2, i.e.:

phi(2^D) = 2^(D-1)

Example. Let

• N = 5
• C = 3
• 2^D = 16
• phi(16) = 8

Choose arbitrarily m = 7 (odd), and compute

3 * 7^(8-5) = 1029
s = 1029 mod 16 = 5

Now

s * m^N = 5 * 7^5 = 84035
84035 mod 16 = 3 == C

Answer 3

Here is a method for computing the values for start and multiplier for the case when constant is odd:

1. Find such odd m (m = multiplier) that order of m modulo 2^D is at least count, meaning that smallest n such that m^n = 1 (mod 2^D) is at least count. I don't know any other way to find such m than to make a random guess, but from a little experimenting it seems that half of odd numbers between 1 and 2^D have order 2^(D-2) which is maximal. (I tried for D at most 12.)

2. Compute x such that x * m^count = 1 (mod 2^D) and set start = x * constant (mod 2^D).

Such x can be found with "extended euclidean algorithm": Given a and b with no common divisor, it gives you x and y such that a * x + b * y = 1. Here a=m^count mod 2^D and b = 2^D.

edit: If constant happens to be even, you can divide it with a power of 2, say 2^k, to make in odd, then do the above for input {constant/2^k, count, 2^(D-k)} and finally return {start*2^k,multiplier}.