multiplication chains that result in a constant modulo a power of 2
-
05-07-2019 - |
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
Solution
Here is a method for computing the values for start and multiplier for the case when constant is odd:
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.)
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}.
OTHER TIPS
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
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.