ライトニング さんが書きました:復号結果の[9] [5] [2] はどのような判定をしてこれが出力されたのでしょうか?
No.55 のプログラムですね。
コード:
printf("暗号: %d\n", xmody);
xmody = (long long)xmody * inverse(y, x) % x;
printf("復号:");
for (i = NUM; --i >= 0; ) {
if (xmody >= kakunou[i]) {
xmody -= kakunou[i];
printf(" [%d]", i);
}
}
printf("\n");
最初の xmody は暗号文です。
これに、(mod x) における y の逆元である inverse(y, x) を掛けて、
その結果を x で割った余りが、秘密鍵である kakunou の部分和です。
ここでは、それをまた xmody に代入しています。
超増加列である kakunou の項の大きいほうから順に、すなわち
kakunou[N-1], kakunou[N-2], ..., kakunou[0] を xmody から、
引けるなら引いて、その位置を表示しています。
これが、MHナップサック暗号の復号手順で、復号した平文の
1の立っているビットの位置だけを表示したものです。
ライトニング さんが書きました:1.(long long)kakunou
コード:
#else // 修正
newkakunou[i] = (long long)kakunou[i] * y % x;
#endif
公開鍵を作るところですね。
NUM が 10 の場合、kakunou
や y は 1万未満の値なので kakunou * y は
1億未満の値となり、32ビットの int でオーバーフローしませんが、たとえば、
NUM が 20 の場合、kakunou や y は 1億未満の値なので kakunou * y は
32ビットの int の最大値である 2147483647 を超えてしまいます。
そこで、掛け算をする前に kakunou の値を (long long) すなわち 64ビットの
int に変換して、y を掛けてもオーバーフローしないようにしています。その
掛け算の結果を y で割ると、また 32ビットの int に収まる小さな値になります。
ライトニング さんが書きました:2.for (i = NUM; --i >= 0; ) {
if (xmody >= kakunou) {
xmody -= kakunou;
printf(" [%d]", i);
既に説明しました。
ライトニング さんが書きました:3.for (;;)
コード:
int get_prime(int sum)
{
int x;
printf("数列の項の合計 = %d\n", sum);
for (;;)
{
printf("x の値は? ");
if (scanf("%d",&x) != 1)
{
exit(1);
}
if (x >= sum)
return x;
else
puts("数列の合計値よりxが小さいです。");
}
}
「for(;;) 文」は「while (1) 文」と同様に、文を繰り返し実行します。
その無限ループからは、return文や break文や exit関数の呼び出しなどで
抜けだします。
ライトニング さんが書きました:4.while (b)
r = a % b, a = b, b = r;
コード:
int gcd(int a, int b)
{
int r;
while (b)
r = a % b, a = b, b = r;
return a;
}
最大公約数を求めるところですね。
次のように書いても同じです。これは説明不要ですよね。
コード:
int gcd(int a, int b)
{
int r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
ライトニング さんが書きました:5.int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
while (z2 > 1)
#define STEP(a, b) (t = a - q * b, a = b, b = t)
q = z1 / z2, STEP(x1, x2), STEP(y1, y2), STEP(z1, z2);
return x2 < 0 ? x2 + b : x2;
コード:
int inverse(int a, int b)
{
int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
while (z2 > 1)
#define STEP(a, b) (t = a - q * b, a = b, b = t)
q = z1 / z2, STEP(x1, x2), STEP(y1, y2), STEP(z1, z2);
return x2 < 0 ? x2 + b : x2;
}
(mod b) における a の逆元を求めるところですね。
#define STEP(a, b) は関数型マクロと言って、これ以降に、STEP という名前が
出てくるところはすべて (t = a - q * b, a = b, b = t) の文字列に置き換え
ますが、引数の a, b は与えられた引数に置き換えます。
ということで次のようになります。
コード:
int inverse(int a, int b)
{
int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
while (z2 > 1)
q = z1 / z2,
(t = x1 - q * x2, x1 = x2, x2 = t),
(t = y1 - q * y2, y1 = y2, y2 = t),
(t = z1 - q * z2, z1 = z2, z2 = t);
return x2 < 0 ? x2 + b : x2;
}
さらに 三項演算子 ? : を if文に置き換えて、分かりやすくすると、
コード:
int inverse(int a, int b)
{
int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
while (z2 > 1) {
q = z1 / z2;
t = x1 - q * x2, x1 = x2, x2 = t;
t = y1 - q * y2, y1 = y2, y2 = t;
t = z1 - q * z2, z1 = z2, z2 = t;
}
if (x2 < 0)
return x2 + b;
else
return x2;
}