math - MOD式で変数値を見つける方法は?

Question

9 = 2^X mod 11

X とは何ですか? X を見つけるにはどうすればよいですか?

RSAアルゴリズムでプレーンテキストを見つけることに関連しており、そのためのCプログラムを書いています。

Answer 1

答えは、任意の整数 i に対して 6 + 10i です。

小さな係数の解を得る簡単な方法は、x のすべての値を反復することです。0 から 10 (= 11 - 1) の間でチェックするだけで、最初の解を見つけることができます (解が存在する場合)。

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

出力：

6
16
26
36
46

モジュラスが大きい場合、明らかに時間がかかります。

詳細については、離散対数のページをご覧ください。ノート：

一般離散対数 logbg を計算するための効率的な古典的アルゴリズムは知られていません。素朴なアルゴリズムは、目的の g が見つかるまで、b を k の累乗にどんどん大きくしていきます。これは試行乗算と呼ばれることもあります。このアルゴリズムは、グループ G のサイズで線形の実行時間を必要とするため、グループのサイズの桁数で指数関数的です。

累乗剰余を簡単に反転できるとしたら、それは優れた暗号化プリミティブではありません。

Answer 2

明らかに、2^n mod 11 のシーケンスは周期的になります。

2^0 mod 11 = 1
2^1 mod 11 = 2
2^2 mod 11 = 4
2^3 mod 11 = 8
2^4 mod 11 = 5
2^5 mod 11 = 10
2^6 mod 11 = 9
2 ^7 mod 11 = 7
2^8 mod 11 = 3
2^9 mod 11 = 6
2^10 mod 11 = 1
2^11 mod 11 = 2

したがって、サイクルの長さは 10 です。

2^n mod 11 = 9 for n=6+10*m m は整数

Answer 3

剰余算術を使用して解決できると思います。もう 1 つの方法は、F ₁₁ (Z/11Z) で 9=2^X を計算することですが、これも剰余演算の一部です。

もう 1 つの解決策 (解決策が 1 つしかない場合) は、方程式を数値的に解くことです。おそらく C プログラムの方が簡単です。