2

「乗算チェーン」を与える実用的なアルゴリズムはありますか

明確にするために、目標は、任意の正確な長さの乗算変更を生成すること
です。長さ 1 の乗算チェーンは自明です。

「乗算チェーン」は、コードで使用される 2 つの数値 {start} と {multiplier} として定義されます。

 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.

3 つのパラメーターを使用するルーチン を見つけたいと思い ます
。

ルーチンは {start} と {multiplier} を返します。

理想的には、0 の {Constant} 値が有効であるべきです。

些細な例:

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

自明でない例: 

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

与えられた 2 のべき乗の最大 {count} はかなり小さい場合があります。
たとえば、2^4 (16) はカウントが 4 に制限されているようです

4

3 に答える 3

5

次の剰余方程式の自明でない解を求めています。

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

どこ

  • s は開始定数です
  • m は乗数です
  • N は反復回数です (問題によって与えられます)
  • C は最終的な定数です (問題によって与えられます)
  • D は 2 の累乗の指数です (問題によって与えられます)。

数論におけるオイラーの定理を見てみましょう。

任意の奇数m (2^D で素数) の場合、次のようになります。

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

したがって

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

そして最後に

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

取った

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

これで完了です。2 の累乗のオイラーのファイ関数は、2 の累乗の半分です。つまり、

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

例。させて

  • N = 5
  • C = 3
  • 2^D = 16
  • ファイ(16) = 8

m = 7 (奇数) を任意に選択し、計算します。

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

今

s * m^N = 5 * 7^5 = 84035
84035 mod 16 = 3 == C
于 2008-11-01T05:26:05.887 に答える
2

定数が奇数の場合の開始値と乗数の値を計算する方法を次に示します。

  1. 2^D を法とする m の次数が少なくとも count になるような奇数の m (m = 乗数) を見つけます。つまり、m^n = 1 (mod 2^D) となるような最小の n は少なくとも count になります。無作為に推測する以外に、そのような m を見つける方法はわかりませんが、少し実験してみると、1 から 2^D までの奇数の半分の次数は 2^(D-2) で、これが最大になるようです。(私は D をせいぜい 12 にしようとしました。)

  2. x * m^count = 1 (mod 2^D) となるように x を計算し、start = x * 定数 (mod 2^D) を設定します。

このような x は、「拡張ユークリッド アルゴリズム」で見つけることができます。公約数のない a と b を指定すると、a * x + b * y = 1 となる x と y が得られます。ここで、a=m^count mod 2^D となります。 b = 2^D。

編集:定数がたまたま偶数の場合、それを 2 の累乗、たとえば 2^k で割って奇数にし、入力 {constant/2^k, count, 2^(Dk)} に対して上記を実行します。最後に {start*2^k,multiplier} を返します。

于 2008-11-01T18:16:59.107 に答える
1

なぜこれが要件を満たさないのでしょうか?

start = constant;
multiplier = 1;

更新: ループの数が入力パラメーターの 1 つであることがわかりました。この問題は、離散対数問題の特殊なケースであるか、少なくとも関連しているように思えます。

于 2008-11-01T04:37:18.793 に答える