格納

[ライトニング]

課題の内容はMH暗号を作るという課題です。
すいません自分のなかでのＭＨ暗号の解釈が大分間違っているのかもしれません。
かずまさんが正しい復号だと思います。申し訳ないです。
ほとんど今までも丸投げ質問でしたが最後の復号部分の作り方を教えていただけないでしょうか？
Ｃ言語の参考書などを読んでるのですがMH暗号を理解するのも難しくそれをプログラミングで作ってみるというのもとても難しく
苦戦してる状態です。

[かずま]

課題の内容はMH暗号を作るという課題です。

「MH暗号を作る」が課題の全文ですか？
こういう入力に対して、こういう出力が表示されるように、
などの指定はないんですか？
プログラミング言語の指定もないんですか？

ほとんど今までも丸投げ質問でしたが最後の復号部分の作り方を教えていただけないでしょうか？

No. 44 のプログラムの 79～88行目と、No.55 のプログラムの 59～67行目で既に
作り方を教えたはずなのですが、見ていないのですか？

分からないところは質問してくれれば、なんでも答えるつもりでいるんですけど。

[かずま]

Ｃ言語の参考書などを読んでるのですがMH暗号を理解するのも難しく

Wikipediaの Merkle-Hellmanナップサック暗号 のページの左側に「他言語版」が
あって「English」を選ぶと、そこには、小学生でもわかりそうな具体的な例が
載っていて、詳しく解説されています。

[かずま]

No.44 のプログラムに、間違い発見。
暗号データを 2進 10ビットで表示していますが、これは公開鍵 b の部分和なので
もっと大きな数です。表示を改めます。
また、r の値をユーザが入力するのではなく、内部で求めるようにしました。

コード:

#include <stdio.h>
#include <stdlib.h>
 
#define N  10
 
int gcd(int a, int b)
{
    int r;
    while (b)
        r = a % b, a = b, b = r;
    return a;
}
 
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;
}
 
void print_array(const char *name, int a[N])
{
    int i;
    printf("%s = [", name);
    for (i = 0; i < N; i++) printf(" %d", a[i]);
    printf(" ]\n");
}
 
void print_bin(const char *name, int b)
{
    int i;
    printf("%s = [", name);
    for (i = N; --i >= 0; ) printf(" %d", b >> i & 1);
    printf(" ]\n");
}
 
int input_data(const char *name, int *a)
{
    int i = 0;
    char buf[256];
    printf("\nEnter %d binary digits\n", N);
    printf("%.*s\n", N, "123456789.123456789.123456789.12");
    if (!fgets(buf, sizeof buf, stdin)) exit(1);
    *a = 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') *a |= 1 << (N - i - 1);
        else if (buf[i] != '0') break;
    return i == N;
}
 
void generate_keys(int b[N], int w[N], int *q, int *r)
{
    int i, sum = 0;
    for (i = 0; i < N; i++)
        sum += w[i] = sum + 1 + rand() % 10;
    *q = sum + 1 + rand() % 10;
    print_array("  w", w);
    printf("  sum = %d\n", sum);
    for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
    for (i = 0; i < N; i++)
        b[i] = (long long)*r * w[i] % *q;
}
 
int encrypt(int a, int b[N])
{
    int i, c = 0;
    for (i = 0; i < N; i++)
        if (a >> (N - i - 1) & 1) c += b[i];
    return c;
}
 
int decrypt(const int c, const int w[N], int q, int r)
{
    int i, s = 0, c1 = (long long)c * inverse(r, q) % q;
    for (i = N; --i >= 0; )
        if (c1 >= w[i]) {
            c1 -= w[i];
            s |= 1 << (N - i - 1);
        }
    return s;
}
 
int main(void)
{
    int w[N], q, r;  // private key
    int b[N];        // public key
    int a;  // input data
    int c;  // encrypted data
    int s;  // decrypted data
 
    generate_keys(b, w, &q, &r);
    printf("Private key\n");
    print_array("  w", w);
    printf("  q = %d\n  r = %d\n", q, r);
    printf("Public key\n");
    print_array("  b", b);
 
    while (input_data("a", &a)) {
        print_bin("  a", a);
        c = encrypt(a, b);
        printf("  c = %d\n", c);
        s = decrypt(c, w, q, r);
        print_bin("  s", s);
    }
    return 0;
}

10ビットの 2進数をいろいろ入力してみてください。

[ライトニング]

指定されたのはC言語です。
内容はとりあえずMH暗号を作れとの事です。

後実行してみたのですが
warning: format string is empty [-Wformat-zero-length]
printf("",sum);
^~
こういうエラーを吐かれてしまったのですがどう直せばいいのでしょうか？

[かずま]

後実行してみたのですが
warning: format string is empty [-Wformat-zero-length]
printf("",sum);
^~
こういうエラーを吐かれてしまったのですがどう直せばいいのでしょうか？

プログラムは複数あります。
どのプログラムを実行したのか書きましょう。

エラーメッセージは、出たものをそのままコピペしましょう。
ファイル名と「行番号」があるはずです。

英語だからといって、内容を読まないのですか？
「警告: 書式文字列がカラです。printf("",sum);」
どう直せばいいかは、No.44 で回答済みです。見ていないんですか？

[ライトニング]

すいませんNo44の通りやったら治りました。すいません。
また復号は公開鍵の中から自分で何か部分和を作りその部分和にxmodyの逆元をかけると秘密鍵の数列の要素の部分和になっているみたいです。
その部分和を秘密鍵の大きい値から順番に引けるか判定をしていき最終的に０になればいいみたいです。

それをNo.55の回答でうまくだしたいのですがどうすればいいのでしょうか？

[ライトニング]

すいませんNo44の通りやったら治りました。すいません。
また復号は公開鍵の中から自分で何か部分和を作りその部分和にxmodyの逆元をかけると秘密鍵の数列の要素の部分和になっているみたいです。
その部分和を秘密鍵の大きい値から順番に引けるか判定をしていき最終的に０になればいいみたいです。

それをNo.55の回答でうまくだしたいのですがどうすればいいのでしょうか？

[かずま]

また復号は公開鍵の中から自分で何か部分和を作りその部分和にxmodyの逆元をかけると秘密鍵の数列の要素の部分和になっているみたいです。

「公開鍵の中から自分で何か部分和を作り」ですか。「何か」はないでしょう。
暗号化したい 10ビットのデータ(これを平文と言います)のうち、1の立っている
ビットが何番目にあるかで、公開鍵の何番目の数値を使うかを決めるんです。
そうしてできた部分和が暗号化データ(暗号文と言います)です。

ここからが復号です。

「xmodyの逆元」という意味不明の用語を使わないでください。
「x を法とする合同の y の逆元」とか「モジュロ x の y の逆元」とか
「mod x における y の逆元」と言いましょう。

暗号データ(部分和)にその「y の逆元」を掛けて、x で割った余りが
秘密鍵の部分和になります。

その部分和を秘密鍵の大きい値から順番に引けるか判定をしていき最終的に０になればいいみたいです。

0 にはなるんです。もっと重要なのは、何番目が引けたかということで、それに
よって 10ビットのデータの何番目が 1 なのかが分かり、元の平文が復号できた
ことになります。

それをNo.55の回答でうまくだしたいのですがどうすればいいのでしょうか？

[9] [5] [2] とうまく出てるじゃないですか。

0010010001 と表示したいということですか？

No.44 の訂正版である No.64 のプログラムの中の decrypt() や print_bin()
を参考にすればいいだけのことでは？

それとも、全部引き終わったらゼロになったことを確認したいのですか？

それなら、No.64 のプログラムでは復号の最後で if (c1 == 0) printf("OK\n");。
No.55 のプログラムなら、if (xmody == 0) printf("OK\n"); でいいのでは？

[ライトニング]

復号結果の[9] [5] [2] はどのような判定をしてこれが出力されたのでしょうか？

また何箇所か理解できない部分があるんですが

1.(long long)kakunou

2.for (i = NUM; --i >= 0; ) {
if (xmody >= kakunou) {
xmody -= kakunou;
printf(" [%d]", i);

3.for (;;)

4.while (b)
r = a % b, a = b, b = r;

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;

この辺りのプログラミングの内容がよくわからないのですがどういう事なのでしょうか？

[かずま]

復号結果の[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;
}

[かずま]

#define STEP(a, b) は関数型マクロと言って、

「関数型マクロ」を「関数形式マクロ」に訂正します。
なお、#define NUM 10 のようなマクロを「オブジェクト形式
マクロ」と言います。これらは、JIS の規格書の用語です。
ISO では、object-like macro と function-like macro でした。

[かずま]

コード:

#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 に収まる小さな値になります。

最後の文を次のように訂正します。

「その掛け算の結果を x で割ると、その余りは 32ビットの int に収まる小さな値になります。」

ところで、このトピックは解決にはならないんでしょうか？
少なくとも次のトピックは解決になっていいと思うんですが。
　数列の作成　と　mody逆演算

[ライトニング]

分かり易い説明ありがとうございます。

intget_primeやintgcdやint inverse　のintの後の部分はどのような名前に変えてもいいんですかね？
関数？との見分けが出来てない部分が何個かありまして...
同様に(long long)xmodyのlong longの部分
void print_suretu(const char *title, const int *kakunou, int num)
const title const int
なども問題ないのでしょうか？

[みけCAT]

intget_primeやintgcdやint inverse　のintの後の部分はどのような名前に変えてもいいんですかね？

C言語の識別子として有効な名前で、他の名前と被らなければいいでしょう。

同様に(long long)xmodyのlong longの部分
void print_suretu(const char *title, const int *kakunou, int num)
const title const int
なども問題ないのでしょうか？

はい。
typedefを用いてC言語の識別子として許される範囲で好きな名前をつけることができます。

[ライトニング]

int get_rand(void);
int get_prime(int sum);
void print_suretu(const char *title, const int *kakunou, int num);

int gcd(int a, int b);
int inverse(int a, int b);

ちなみに最初のこの部分を全部消しても動いたのですが
この部分自体も別に分かりやすく書いてるだけでいらないということでしょうか？

[みけCAT]

int get_rand(void);
int get_prime(int sum);
void print_suretu(const char *title, const int *kakunou, int num);

int gcd(int a, int b);
int inverse(int a, int b);

ちなみに最初のこの部分を全部消しても動いたのですが
この部分自体も別に分かりやすく書いてるだけでいらないということでしょうか？

NO: 55のコードなら、代わりにmain関数を一番下に持ってくれば、消してもいいでしょう。

[かずま]

intget_primeやintgcdやint inverse　のintの後の部分はどのような名前に変えてもいいんですかね？
関数？との見分けが出来てない部分が何個かありまして...

intget_prime ではなく、int get_prime ですね。質問は正確に書きましょう。
これは int に関連する名前を宣言しているところです。
名前は、英字で始まり英数字が続くという規則に従えば何でも構いません。
英字には、下線を含みます。だから、get_prime は OK。

int get_prime; と書けば、get_prime は int型の変数です。
int get_prime(int sum); と書けば、get_prime は、int型の値を返す関数です。
これらの宣言で、名前が変数名か関数名か、が分かります。
名前の後に ( がついている宣言の時は、その名前は関数名です。
見分けができてない部分とは具体的にどこでしょうか？

同様に(long long)xmodyのlong longの部分

同様にというのは、long long の部分をどのような名前に書き換えてもよいか、
ということでしょうか？
それはダメです。long long は C のキーワードであり、型名です。
No.55 のプログラムでは、int が 32ビット、long long が 64ビットであるもの
と仮定しています。たいていのコンパイラは、そのようになっていますが、
int が 16ビットのものや、long が 64ビットのものもあります。

void print_suretu(const char *title, const int *kakunou, int num)
const title const int
なども問題ないのでしょうか？

これは、質問が不明確です。const title const int って何ですか？
const char *title の const char * は型を表すので変更できません。
title は名前ですから、変更してかまいません。

[かずま]

int get_rand(void);
int get_prime(int sum);
void print_suretu(const char *title, const int *kakunou, int num);

int gcd(int a, int b);
int inverse(int a, int b);

ちなみに最初のこの部分を全部消しても動いたのですが
この部分自体も別に分かりやすく書いてるだけでいらないということでしょうか？

動きますが、コンパイル時に警告が出るでしょう。
VC++ なら、

コード:

C:\tmp>cl hm2.c
Microsoft(R) C/C++ Optimizing Compiler Version 18.00.31101 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

hm2.c
hm2.c(97) : error C2371: 'print_suretu' : 再定義されています。異なる基本型です。

cygwin の gcc なら、

コード:

C:\tmp>gcc hm2.c
hm2.c:96:6: 警告: 'print_suretu' と型が競合しています
 void print_suretu(const char *title, const int *kakunou, int num)
      ^
hm2.c:51:5: 備考: 前の 'print_suretu' の暗黙的な宣言はここです
     print_suretu("秘密鍵: ", kakunou, NUM);

あなたの使っているコンパイラは何ですか？

あなたは，他にも、回答者からの多くの質問を無視して答えていませんね。
できるだけ答えてください。

それから、No.64 のプログラムは、ちゃんと見ていますか？
Wikipediaの Merkle-Hellmanナップサック暗号に書いてる通りに
実装しているつもりなので、分かりやすいはずです。
No.55 のプログラムは、変数名が kakunou、newkakunou、x、y、xmody と
意味不明のものばかりで、よくないと思いませんか？
暗号化する平文がプログラムの中に埋め込まれているし、
その埋め込み方も結果の表示もビット列ではなく、
1のビットの番号だけというのは変だと思いませんか？

[ライトニング]

すみません自分の中で勝手に回答したつもりでした。
コンパイラはC言語のフリーソフト？みたいなのと
gcc でターミナルでやっています。

No64の回答していただいのは自分の理解力がなくてどの部分がどういう動きになってるのかよくわからなくて
またコンパイルした後何をしたらいいのかもよくわからなくて...

後一つ数列の合計値は？までに出てくる最初の数列と
xの値とyの値を入力した後に出てくる秘密鍵の数列が変わってしまうのですがどうすれば良いのでしょうか？

[ライトニング]

またライブラリを使って大きい桁でやってみたいのですがどこの値を変えたらたくさんの乱数を生成できるのでしょうか？

[ライトニング]

NTLというライブラリを使って実行してみたのですが
#define NUM 10を#define NUM 30に
return rand() % 10 + 1;をreturn rand() % 30 + 1;
に変えて実行してみたのですが合計値が−になりうまくきいきませんでした

[かずま]

コンパイラはC言語のフリーソフト？みたいなのと
gcc でターミナルでやっています。

答えはそれだけですか？

あなたは、No.55 のプログラムで、先頭の「関数の宣言」を削除しても
動いたので、これは要らないということか、と聞いてきました。
でも削除するとコンパイラが警告を出すはずなのに、それは書いていません。
だから、どんなコンパイラを使っているのかと尋ねたのです。
そしたら、gcc だという。
質問です。警告は出なかったのですか？
警告は出たけれど、動けばいいと判断したのでしょうか？

No64の回答していただいのは自分の理解力がなくてどの部分がどういう動きになってるのかよくわからなくて
またコンパイルした後何をしたらいいのかもよくわからなくて...

コンパイルした後は、実行でしょう。

実行例

コード:

  w = [ 2 10 17 30 69 133 270 540 1074 2150 ]
  sum = 4295
Private key
  w = [ 2 10 17 30 69 133 270 540 1074 2150 ]
  q = 4301
  r = 2150
Public key
  b = [ 4300 4296 2142 4286 2116 2084 4166 4031 3764 3226 ]

Enter 10 binary digits
123456789.
0011010110
  a = [ 0 0 1 1 0 1 0 1 1 0 ]
  c = 16307
  s = [ 0 0 1 1 0 1 0 1 1 0 ]

Enter 10 binary digits
123456789.
0000101101
  a = [ 0 0 0 0 1 0 1 1 0 1 ]
  c = 13539
  s = [ 0 0 0 0 1 0 1 1 0 1 ]

Enter 10 binary digits
123456789.
.

実行すると、超増加列とその合計値を表示し、
さらに秘密鍵と公開鍵を生成して表示します。そして
Enter 10 binary digits
123456789.
と表示して、10個の2進数字を入力せよと言ってきます。
123456789. は間違いなく 10個の数字(0 か 1) を入力するためのガイドです。
10ビットの 2進数を入力すると、それを平文 a として表示し、
暗号化して、c の値として表示し、復号して s を表示します。
a から c へは公開鍵を使って暗号化され、
c から s へは秘密鍵を使って復号されています。

で、質問です。No.64 のプログラムは見てもよくわからないから、
実行してみなかったのですか？

後一つ数列の合計値は？までに出てくる最初の数列と
xの値とyの値を入力した後に出てくる秘密鍵の数列が変わってしまうのですがどうすれば良いのでしょうか？

これはどのプログラムのことを言っていますか？
No.55 も No.64 も「数列の合計値は？」とは表示しません。
最初の数列とは何ですか？
新しいプログラムなら、それを提示してください。また実行経過を
[ code=text] と [ /code] で挟んで提示してください。
具体的なデータを示してもらわないと、数列が変わってしまうといわれても
何のことかわかりません。

[かずま]

またライブラリを使って大きい桁でやってみたいのですがどこの値を変えたらたくさんの乱数を生成できるのでしょうか？

「大きい桁」とは何桁ぐらい？
「どこの値を変えたら」というのは、No.55 のプログラムで、
と言っているのですか？

[かずま]

NTLというライブラリを使って実行してみたのですが

実行したプログラムを提示してくれないことには、何も言えません。

質問です。NTL は C++ のライブラリなのではありませんか？
int や long long では桁数が少ないので、新しい型と演算子を定義して
提供するライブラリではないのですか？

[かずま]

No64の回答していただいのは自分の理解力がなくてどの部分がどういう動きになってるのかよくわからなくて

No.64 のプログラムが理解されないのは、
入力データである 10個の 1 と 0 を本当の 10ビットのデータに変換して
int の a に入れるビット操作が分かりにくいのだと考えました。
そこで、int a[N]; と配列にして、その要素に 1 か 0 を入れることにしました。
以後は、Wikipediaの Merkle-Hellmanナップサック暗号 を参照しながら、
次のプログラムをよく読んでみてください。

コード:

#include <stdio.h>   // fgets, printf
#include <stdlib.h>  // rand, srand
#include <time.h>    // time

#define N  10

int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b)
        r = a % b, a = b, b = r;
    return a;
}

int inverse(int a, int b)  // b を法とする整数の合同における a の逆元
{
    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;
}

void print_array(const char *name, const int a[N]) // 配列の表示
{
    int i;
    printf("%s = [", name);
    for (i = 0; i < N; i++) printf(" %d", a[i]);
    printf(" ]\n");
}

int input_data(int a[N])  // データの入力
{
    int i;
    char buf[256];
    printf("\nEnter %d binary digits\n", N);
    printf("%.*s\n", N, "123456789.123456789.123456789.12");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i == N;  // i が N だったら 1 を、そうでなかったら 0 を返す
}

void generate_keys(int b[N], int w[N], int *q, int *r)  // 鍵の生成
{
    int i, sum = 0;
    for (i = 0; i < N; i++)  // 超増加列(秘密鍵)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w);
    printf("  sum = %d\n", sum);
    *q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;  // 秘密鍵 r の生成
    for (i = 0; i < N; i++)  // 公開鍵の生成
        b[i] = (long long)*r * w[i] % *q;
}

int encrypt(const int a[N], const int b[N])  // 暗号化
{
    int i, c = 0;
    for (i = 0; i < N; i++)
        if (a[i] == 1) c += b[i];
    return c;
}

int decrypt(int c, const int w[N], int q, int r, int s[N])  // 復号
{
    int i, sum = (long long)c * inverse(r, q) % q;
    for (i = N; --i >= 0; ) {
        if (sum >= w[i])
            sum -= w[i], s[i] = 1;
        else
            s[i] = 0;
    }
    return sum; // 復号できれば 0、そうでなければ正の値を返す
}

int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ

    srand(time(0));
    generate_keys(b, w, &q, &r); // 鍵の生成
    printf("Private key\n");
    print_array("  w", w);
    printf("  q = %d\n  r = %d\n", q, r);
    printf("Public key\n");
    print_array("  b", b);

    while (input_data(a)) {      // データの入力
        print_array("  a", a);   // 入力データの表示
        c = encrypt(a, b);       // 暗号化
        printf("  c = %d\n", c); // 暗号化されたデータの表示
        decrypt(c, w, q, r, s);  // 復号
        print_array("  s", s);   // 復号されたデータの表示
    }
    return 0;
}

分からないところは質問してください。
inverse() の中身は分からなくてかまいません。

[ライトニング]

コード:

#include<NTL/zz.h>
using namespace std;
using namespace NTL;

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NUM 10
 
zz get_rand(void); 
zz get_prime(zz sum); 
void print_suretu(const char *title, const int *kakunou, int num); 

zz gcd(int a, int b);
zz inverse(int a, int b);

 
void main()
{
    zz i, sum;
    zz kakunou[NUM], newkakunou[NUM], suretu;
    zz x, y, xmody;
    srand((unsigned int)time(NULL));
 
   
    sum = 0;
    for (i = 0; i < NUM; i++)
    {
        suretu = sum + get_rand();
        sum = sum + suretu;
        kakunou[i] = suretu;
    }
     x = get_prime(sum);
    while (1) {
        printf("y の値は? "); scanf("%d", &y);
        if (gcd(x, y) == 1) break;
        printf("x と y が互いに素ではありません。\n");
    }
    for (i = 0; i < NUM; i++)
    {

        newkakunou[i] = kakunou[i] * xmody;

        newkakunou[i] = (long long)kakunou[i] * y % x;

    }
 
    print_suretu("秘密鍵: ", kakunou, NUM);
    printf("合計 = %d, x = %d, y = %d\n", sum, x, y);
    print_suretu("公開鍵: ", newkakunou, NUM);
    printf("暗号%d",newkakunou[2]+newkakunou[5]+newkakunou[9]);
    xmody = newkakunou[2]+newkakunou[5]+newkakunou[9];
    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");
    return 0;
}
 
zz get_rand(void)
{
    return rand() % 10 + 1;
}
 
zz get_prime(int sum)
{
    zz x;
    printf("数列の項の合計 = %d\n", sum);
    for (;;)
    {
        printf("x の値は? ");
        if  (scanf("%d",&x) != 1)
        {
           
            exit(1);
        }
        if (x >= sum)
            return x;
        else
            puts("数列の合計値よりxが小さいです。");
    }
}
 
void print_suretu(const char *title, const int *kakunou, int num)
{
    zz i;
    for (i = 0; i < num; i++)
    {
        printf("%s%d", i == 0 ? title : ", ", kakunou[i]);
    }
    putchar('\n');
}
 
zz gcd(int a, int b)
{
    int r;
    while (b)
        r = a % b, a = b, b = r;
    return a;
}
 
zz inverse(zz a, zz b)
{
    zz 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;
}
 

これをNTLライブラリを使って実行したのですが
zz get_rand(void);
^
mhangou.cpp:12:1: error: unknown type name 'zz'
zz get_prime(zz sum);
^
mhangou.cpp:12:14: error: unknown type name 'zz'
zz get_prime(zz sum);
^
mhangou.cpp:15:1: error: unknown type name 'zz'
zz gcd(int a, int b);
^
mhangou.cpp:16:1: error: unknown type name 'zz'
zz inverse(int a, int b);
^
mhangou.cpp:19:1: error: 'main' must return 'int'
void main()
^~~~
int
mhangou.cpp:21:5: error: unknown type name 'zz'
zz i, sum;
^
mhangou.cpp:22:5: error: unknown type name 'zz'
zz kakunou[NUM], newkakunou[NUM], suretu;
^
mhangou.cpp:23:5: error: unknown type name 'zz'
zz x, y, xmody;
^
mhangou.cpp:27:5: error: use of undeclared identifier 'sum'
sum = 0;
^
mhangou.cpp:30:9: error: use of undeclared identifier 'suretu'
suretu = sum + get_rand();
^
mhangou.cpp:30:18: error: use of undeclared identifier 'sum'; did you mean
'sub'?
suretu = sum + get_rand();
^~~
sub
/usr/local/include/NTL/zz.h:322:13: note: 'sub' declared here
inline void sub(ZZ& x, const ZZ& a, const ZZ& b)
^
mhangou.cpp:30:22: error: arithmetic on a pointer to the function type 'void
(NTL::ZZ &, const NTL::ZZ &, const NTL::ZZ &)'
suretu = sum + get_rand();
~~~ ^
mhangou.cpp:31:9: error: use of undeclared identifier 'sum'
sum = sum + suretu;
^
mhangou.cpp:31:15: error: use of undeclared identifier 'sum'; did you mean
'sub'?
sum = sum + suretu;
^~~
sub
/usr/local/include/NTL/zz.h:322:13: note: 'sub' declared here
inline void sub(ZZ& x, const ZZ& a, const ZZ& b)
^
mhangou.cpp:31:21: error: use of undeclared identifier 'suretu'
sum = sum + suretu;
^
mhangou.cpp:32:22: error: use of undeclared identifier 'suretu'
kakunou = suretu;
^
mhangou.cpp:34:20: error: use of undeclared identifier 'sum'; did you mean
'sub'?
x = get_prime(sum);
^~~
sub
/usr/local/include/NTL/zz.h:322:13: note: 'sub' declared here
inline void sub(ZZ& x, const ZZ& a, const ZZ& b)
^
mhangou.cpp:34:10: error: no matching function for call to 'get_prime'
x = get_prime(sum);
^~~~~~~~~
mhangou.cpp:12:4: note: candidate function not viable: no known conversion from
'void (NTL::ZZ &, const NTL::ZZ &, const NTL::ZZ &)' to 'int' for 1st
argument
zz get_prime(zz sum);

このようなエラーが出ました。C＋＋との違いがよくわからないのですがzzという型数を宣言したのですがうまくいきません。

大きい桁というとはとりあえず５０ビット？くらいで試してみたい状況です。

[よもやま]

コード:

zz get_rand(void); 
^
mhangou.cpp:12:1: error: unknown type name 'zz'

NTLライブラリのリファレンスやサンプルを参照していないように見受けられます。
zzではなくZZでは。

[かずま]

コード:

#include <iostream>  // cin, cout
#include <cstdlib>   // rand, srand
#include <ctime>     // time
#include <NTL/ZZ.h>

using namespace std;
using namespace NTL;
 
#define N  128
 
ZZ gcd(ZZ a, ZZ b)    // 最大公約数
{
    ZZ r;
    while (b != 0)
        r = a % b, a = b, b = r;
    return a;
}
 
ZZ inverse(ZZ a, ZZ b)  // b を法とする整数の合同における a の逆元
{
    ZZ x1, y1, z1 = a, x2, y2, z2 = b, q, t;
    x1 = 1, y1 = 0, x2 = 0, y2 = 1;
    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;
}
 
void print_array(const char *name, const ZZ *a, int n) // 配列の表示
{
    cout << name << " = [";
    if (n > 10) n = 10;
    for (int i = 0; i < n; i++) cout << ' ' << a[i];
    cout << " ... ]\n";
}
 
void print_bin(const char *name, const int *a, int n) // 配列の表示
{
    cout << name << " = [";
    for (int i = 0; i < n; i++) cout << a[i];
    cout << " ]\n";
}
 
int input_data(int *a)  // データの入力
{
    string buf;
    cout << "\nEnter less than " << N << " binary digits\n";
    if (!getline(cin, buf)) return 0;
    size_t i, n = buf.size();
    if (n >= N) return 0;
    for (i = 0; i < n; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    if (i != n) return 0;
    return n;  // ビット数を返す
}
 
void generate_keys(ZZ *b, ZZ *w, ZZ& q, ZZ& r)  // 鍵の生成
{
    ZZ sum;
    sum = 0;
    for (int i = 0; i < N; i++)  // 超増加列(秘密鍵)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w, N);
    cout << "  sum = " << sum << endl;
    q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (r = q / 2; gcd(r, q) != 1; ++r) ;  // 秘密鍵 r の生成
    for (int i = 0; i < N; i++)  // 公開鍵の生成
        b[i] = r * w[i] % q;
}
 
ZZ encrypt(int n, const int *a, const ZZ *b)  // 暗号化
{
    ZZ c;
    c = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == 1) c += b[i];
    return c;
}
 
int decrypt(int n, ZZ c, const ZZ *w, ZZ q, ZZ r, int *s)  // 復号
{
    ZZ sum = c * inverse(r, q) % q;
    for (int i = n; --i >= 0; ) {
        if (sum >= w[i])
            sum -= w[i], s[i] = 1;
        else
            s[i] = 0;
    }
    return sum != 0; // 復号できれば 0、そうでなければ 1 を返す
}
 
int main(void)
{
    ZZ w[N], q, r;  // 秘密鍵
    ZZ b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    ZZ c;      // 暗号化されたデータ
    int s[N];  // 復号されたデータ
    int n;     // ビット数
 
    srand(time(0));
    generate_keys(b, w, q, r); // 鍵の生成
    cout << "Private key\n";
    print_array("  w", w, N);
    cout << "  q = " << q << "\n  r = " << r << endl;
    cout << "Public key\n";
    print_array("  b", b, N);
 
    while (n = input_data(a)) {    // データの入力
        print_bin("  a", a, n);        // 入力データの表示
        c = encrypt(n, a, b);          // 暗号化
        cout << "  c = " << c << endl; // 暗号化されたデータの表示
        decrypt(n, c, w, q, r, s);     // 復号
        print_bin("  s", s, n);        // 復号されたデータの表示
    }
    return 0;
}

実行結果

コード:

  w = [ 8 14 31 57 114 233 458 917 1839 3672 ... ]
  sum = 2442393501432829254771146219802651424984
Private key
  w = [ 8 14 31 57 114 233 458 917 1839 3672 ... ]
  q = 2442393501432829254771146219802651424992
  r = 1221196750716414627385573109901325712497
Public key
  b = [ 8 14 1221196750716414627385573109901325712527 1221196750716414627385573109901325712553 114 1221196750716414627385573109901325712729 458 1221196750716414627385573109901325713413 1221196750716414627385573109901325714335 3672 ... ]

Enter less than 128 binary digits
0011010100001111010101010011
  a = [0011010100001111010101010011 ]
  c = 10990770756447731646470157989113456852191
  s = [0011010100001111010101010011 ]

Enter less than 128 binary digits
1111111111111111000000000000000000010101010
  a = [1111111111111111000000000000000000010101010 ]
  c = 14654361008596975528626877339778500203434
  s = [1111111111111111000000000000000000010101010 ]

Enter less than 128 binary digits
.

No.83 の質問(？が付いているもの)にすべて答えていただけない場合、
これ以上の質問を受け付けません。
また、以前のトピックを解決にするかどうかも教えてください。

さらに、NTL に関する質問をするなら、
「NTL を使用する Merkle-Hellmanナップサック暗号」という件名の
新しいトピックを立ててください。

[ライトニング]

自宅ではEasyIDECと言うのを使用しておりそれで先頭の「関数の宣言」を消しては実行できました。
学校ので使ってるのEmacsをターミナルでコンパイルするとかずまんの言われたとおり警告が出てしまいました。
なので先頭の「関数の宣言」は消さない事にしました。報告を忘れていました。

No64の実行をしてみたのですがその後どのような値を入力するのか分からないのが謎でした。
けれど10bitを何かうつというのをようやく理解でき実行部分までは理解することができました。

実行したのはこのプログラミングです

コード:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NUM 10
 
int get_rand(void); 
int get_prime(int sum); 
void print_suretu(const char *title, const int *kakunou, int num); 

int gcd(int a, int b);
int inverse(int a, int b);

 
int main(void)
{
    int i, sum;
    int kakunou[NUM], newkakunou[NUM], suretu;
    int x, y, xmody;
    srand((unsigned int)time(NULL));
 
   
    sum = 0;
    for (i = 0; i < NUM; i++)
    {
        suretu = sum + get_rand();
        sum = sum + suretu;
        kakunou[i] = suretu;
        printf("%d\n",sum);
    }
     x = get_prime(sum);
    while (1) {
        printf("y の値は? "); scanf("%d", &y);
        if (gcd(x, y) == 1) break;
        printf("x と y が互いに素ではありません。\n");
    }
    for (i = 0; i < NUM; i++)
    {

        newkakunou[i] = kakunou[i] * xmody;

        newkakunou[i] = (long long)kakunou[i] * y % x;

    }
 
    print_suretu("秘密鍵: ", kakunou, NUM);
    printf("合計 = %d, x = %d, y = %d\n", sum, x, y);
    print_suretu("公開鍵: ", newkakunou, NUM);
    printf("暗号%d",newkakunou[2]+newkakunou[5]+newkakunou[9]);
    xmody = newkakunou[2]+newkakunou[5]+newkakunou[9];
    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");
    return 0;
}
 
int get_rand(void)
{
    return rand() % 10 + 1;
}
 
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が小さいです。");
    }
}
 
void print_suretu(const char *title, const int *kakunou, int num)
{
    int i;
    for (i = 0; i < num; i++)
    {
        printf("%s%d", i == 0 ? title : ", ", kakunou[i]);
    }
    putchar('\n');
}
 
int gcd(int a, int b)
{
    int r;
    while (b)
        r = a % b, a = b, b = r;
    return a;
}
 
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;
}
 

以前に質問した２９行目のprintf("",sum）だとエラーをはかれてしまったのでprintf("%d\n",sum）を治したらこのようになってしまい
[ code=text]
6
17
42
92
193
394
791
1589
3185
6379
数列の合計　= 6379
ｘの値は？　7000
yの値は？　699
秘密鍵　6,11,25,50,101,397,798,1596,3194
合計＝6379 x = 7000 y=6999
公開鍵　6994,6989,6975,6950,6899 6799 6603 6202 5450 3806
暗号　17580 暗号:17580
復号:[9][5][2]
[ /code]
のように少し変になってしました。

すいません。ＮＴＬのことも色々聞きたいので新しいトピックを作らせてもらいます。そちらでよろしくお願いします。

[みけCAT]

オフトピック

学校ので使ってるのEmacsをターミナルでコンパイルするとかずまんの言われたとおり警告が出てしまいました。

Emacsをコンパイルした…？どうして…？

実行したのはこのプログラミングです

これはプログラミングではありません。プログラムです。

[ライトニング]

すいません誤字・脱字がありました。
かずまさんの言われた通り警告が出てしました。
EasyIDEXでは実行できたので勝手にEmacs作ったもの保存したものをgccでもコンパイルできると思い込んでいました。
そのため先頭の関数宣言は消さずにそのままにしておきました。
10bitの何かではなく10個の2進数字を入力をするというのが分かったので実行方法までは分かりました。

[ライトニング]

すいません何て言えばいいのか分からないのですが
Emacsで作ったプログラムをターミナルを使ってgccでコンパイルしましたと言えばいいのでしょうか？説明が下手で申し訳ないです。
すいません実行したプログラムです。

[かずま]

自宅ではEasyIDECと言うのを使用しておりそれで先頭の「関数の宣言」を消しては実行できました。

私のところで、EasyIDEC Ver 0.0.9.0 を起動し、No.90 のプログラムをコピペして、
「プログラム実行」を押すと、次のようにエラーになりました。

コード:

ファイル「C:/EasyIDEC/project/default/main.c」の
「89行目」で記述エラーを発見しました。
「print_suretu」が再定義されています。以前と同じ名前を使っていないか、関数の記述順番は正しいかどうかを確認してください。

gcc では警告だけで実行はできたのに、EasyIDEC ではエラーで実行できません。
EasyIDEC のバージョンが違うのでしょうか？

No64の実行をしてみたのですがその後どのような値を入力するのか分からないのが謎でした。
けれど10bitを何かうつというのをようやく理解でき実行部分までは理解することができました。

No.64 の改良版の No.86 なら中身を理解できますか？
分からないところは質問してください。
No.89 は、これの NTL版です。

実行したのはこのプログラミングです

以前に質問した２９行目のprintf("",sum）だとエラーをはかれてしまったのでprintf("%d\n",sum）を治したらこのようになってしまい

コード:

6
17
42
92
193
394
791
1589
3185
6379
数列の合計　= 6379
ｘの値は？　7000
yの値は？　699
秘密鍵　6,11,25,50,101,397,798,1596,3194
合計＝6379 x = 7000 y=6999
公開鍵　6994,6989,6975,6950,6899 6799 6603 6202 5450 3806
暗号　17580 暗号:17580
復号:[9][5][2]

のように少し変になってしました。

何も変ではありません。
6 17 42 92 というのは sum の値です。
6 11 25 50 というのは、kakunou の値です。

17 = 6 + 11
42 = 6 + 11 + 25
92 = 6 + 11 + 25 + 50
となるのは当然です。プログラムをそうなるように書いているのですから。

[かずま]

私のところで、EasyIDEC Ver 0.0.9.0 を起動し、No.90 のプログラムをコピペして、
「プログラム実行」を押すと、次のようにエラーになりました。

次のように訂正します。

私のところで、EasyIDEC Ver 0.0.9.0 を起動し、No.90 のプログラムをコピペして、
「関数の宣言」を削除して、「プログラム実行」を押すと、次のようにエラーになりました。

[ライトニング]

自分ももう一度改めて実行してみたところかずまさんと同じようなエラーをはかれてしまいました
自分でも何故以前実行できたのか分からない状態です....

またNo.89のプログラムで質問したいことがあるのですがここで質問していいでしょうか？一応ＮＴＬトピックをたてたのですが...

[かずま]

自分ももう一度改めて実行してみたところかずまさんと同じようなエラーをはかれてしまいました
自分でも何故以前実行できたのか分からない状態です....

No.94 の「EasyIDEC のバージョンが違うのでしょうか？」という質問に
答えてもらっていません。

またNo.89のプログラムで質問したいことがあるのですがここで質問していいでしょうか？

No.94 の「No.64 の改良版の No.86 なら中身を理解できますか？」に
答えてもらっていません。
No.89 のプログラムは、No.86 を元に NTL を使うようにしたものなので、
そちらの理解が先です。

一応ＮＴＬトピックをたてたのですが...

No.89 で、「さらに、NTL に関する質問をするなら、
「NTL を使用する Merkle-Hellmanナップサック暗号」という件名の
新しいトピックを立ててください。」とお願いしたのに、そうなっていません。

何度同じ間違いをしたら気が済むのですか？

10/04～10/07 「mod計算？」
10/08～10/14 「数列の作成」
10/23～現在 「格納」
10/29～10/31 「mody逆元計算」

どれも、不明確な質問をし、回答者が疑問を持ってから、Wikipedia の
「Merkle-Hellmanナップサック暗号」へのリンクを持ち出しています。

12/06 「NTLの使い方」

これをＮＴＬでうまく実装させたいのですがどの部分を直せばいいでしょうか？
うか？NTLのオリジナル？の関数なのでしょうか？

これを見た人はどう思いますか？
・このプログラムは何だろうか？
・NTL って何だろうか？
・なぜ直さないといけないんだろうか？
と疑問がいっぱいです。
ちゃんとこれまでの経緯を説明し、少なくとも「格納」へのリンクを張るべきです。

またCとＣ＋＋の違いがよくわからないのですがcoutと言うのはＣ＋＋関数なのでしょうか？NTLのオリジナル？の関数なのでしょうか？

C++ を全く学習していないことが分かります。
せめて 30分だけでも C++ の入門ページを見てください。

[ライトニング]

EasyIDEC のバージョンは一緒でした。

No.86のプログラムを理解できていない状態なのでそちらを聞いてもいいでしょうか？

トピックのタイトルは完全に忘れていました。申し訳ないです。

どれも自分の説明不足で結果的にナップサック暗号のリンクを持ち出してしまってる形になっているのはすいません。

確かにまたＮＴＬのトピックも同じように自分の説明不足でＮＴＬが何のかなども分からない事だらけだと思います。
格納のリンクを貼るべきでした

Ｃ＋＋の入門を少し拝見しcoutがＣ＋＋の関数ということも分かりました。

[みけCAT]

Ｃ＋＋の入門を少し拝見しcoutがＣ＋＋の関数ということも分かりました。

どこでそんなことを知ったのですか？coutは関数ではありません。
c++ - cout and cin are not functions, so what are they? - Stack Overflow

[かずま]

No.86のプログラムを理解できていない状態なのでそちらを聞いてもいいでしょうか？

はい、聞かれたことはなんでも答えるつもりです。

どれも自分の説明不足で結果的にナップサック暗号のリンクを持ち出してしまってる形になっているのはすいません。

そうです。最初にリンクを示し、自分がどんな問題で困っているのかを説明するべきでした。

確かにまたＮＴＬのトピックも同じように自分の説明不足でＮＴＬが何のかなども分からない事だらけだと思います。

NTL は、どこで知ったのですか？
前の課題は、「C言語で MH暗号を作れ」だったと思いますが、
今度の課題は、「C++ で、NTL を使って MH暗号を作れ」になったんですか？

格納のリンクを貼るべきでした

「NTLの使い方」にそのトピックができたいきさつを説明し、リンクを貼ってください。

Ｃ＋＋の入門を少し拝見しcoutがＣ＋＋の関数ということも分かりました。

cout は、オブジェクトです。ostreamクラスのインスタンスです。
と言っても、わからないでしょう。cout は、変数だと思ってください。

cout << "abc" は、operator<<(cout, "abc") のことで、operator<< が関数です。
これは C の fputs("abc", stdout) に相当します。

[ライトニング]

コード:

 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;
 

まずこれがどうしても何故これb を法とする整数の合同における a の逆元が求まるのかが全く分からないです。

コード:

void print_array(const char *name, const int a[N]) // 配列の表示
{
    int i;
    printf("%s = [", name);
    for (i = 0; i < N; i++) printf(" %d", a[i]);
    printf(" ]\n");
 

またvoid print_array aとa[N]の違い　nameは何を表してるのか二行目と四行目のprintfは何を表示させてるのかが分からないです。

コード:

 int i;
    char buf[256];
    printf("\nEnter %d binary digits\n", N);
    printf("%.*s\n", N, "123456789.123456789.123456789.12");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
 

この部分は何をやってるかが全くわからない状態です。　char buf[256]は256bit分箱があると考えればいいですか？

コード:

print_array("  w", w);
for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
 b[i] = (long long)*r * w[i] % *q;
  

この三つがwを何を表してるのか、　for文がどのようになってるのか　bには何の計算が行われてbに何が入ったのかが分からないです。

後最後のほうの while (input_data(a))
input_data(a)になるまで続ける？と言うのがよく分からないです。
この部分のどこを変換したらbit数をかえれるのでしょうか？
ご回答よろしくお願いします。

またNTLをしったのはちゃんと暗号を使える？大きいbit数でもできるように新たなＮＴＬでも動くようにと課題が与えられました。
これのＮＴＬを使って実装の後にもまた別の最後の課題が与えられまずはこっちを理解しなければならない状態です。

[かずま]

コード:

print_array("  w", w);
for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
 b[i] = (long long)*r * w[i] % *q;
  

この三つがwを何を表してるのか、　for文がどのようになってるのか　bには何の計算が行われてbに何が入ったのかが分からないです。

Wikipedia とプログラムに書いてありますが、それでも w や b が何か分かりませんか？
b は beta、すなわち β です。

コード:

int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ
 
    srand(time(0));
    generate_keys(b, w, &q, &r); // 鍵の生成

コード:

void generate_keys(int b[N], int w[N], int *q, int *r)  // 鍵の生成
{
    int i, sum = 0;
    for (i = 0; i < N; i++)  // 超増加列(秘密鍵)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w);
    printf("  sum = %d\n", sum);
    *q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;  // 秘密鍵 r の生成
    for (i = 0; i < N; i++)  // 公開鍵の生成
        b[i] = (long long)*r * w[i] % *q;
}

q や r の実体は、main() の中にあり、
generate_keys() からそれらを参照するために *q や *r となっています。

つづく

[かずま]

つづく

for文ですが、これは右側にあるコメントのように秘密鍵 r の生成です。
Wikipedia には、「整数 r を gcd(r,q) = 1 となるようにランダムに選ぶ」とあります。
ランダムといっても 0 と 1 はダメです。
0 だと、公開鍵が全部 0 になってしまいます。
1 だと、公開鍵が秘密鍵と同じになってしまいます。
2, 3, 4, ... といった小さい数だと r * w が q を超えず、
b[0], b[1], b[2], ... が超増加列なって、秘密鍵がばれやすくなりますから、
ある程度の大きさが必要です。
r が大きすぎると、r * w[N-1] などがオーバーフローする恐れがあります。
そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。

[かずま]

コード:

void print_array(const char *name, const int a[N]) // 配列の表示
{
    int i;
    printf("%s = [", name);
    for (i = 0; i < N; i++) printf(" %d", a[i]);
    printf(" ]\n");
 

またvoid print_array aとa[N]の違い　nameは何を表してるのか二行目と四行目のprintfは何を表示させてるのかが分からないです。

No.86のプログラムを実行すると、次のような表示が出ます。

コード:

  w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
  sum = 6229
Private key
  w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
  q = 6233
  r = 3116
Public key
  b = [ 3114 3110 6219 6209 6185 6135 6038 2727 2338 1558 ]

Enter 10 binary digits
123456789.

最初の行は、generate_array() の中の print_array(" w", w); という
関数呼び出しにより表示されています。
name が、" w" を表していることに何の疑問があるのでしょうか？
関数 print_array() の中の
一つ目の printf で、" w = [" を表示し、
二つ目の printf で、" 5 13 28 48 96 196 390 779 1557 3117" を表示し、
三つ目の printf で、"]\n" を表示しています。

a と a[N] の違いですか？
a は、配列 a の i番目の要素を参照しています。
a[N] は、引数の宣言で、a が配列であることを示しています。
実は、この引数の const int a[N] は、
const int a[] と書いてもよく、
const int *a と書いてもよいのです。
ここでの配列の実体は、main() の int w[N] で、それが generate_keys()
を経由して、print_array() から a で参照できるようになっています。

[かずま]

この部分は何をやってるかが全くわからない状態です。　char buf[256]は256bit分箱があると考えればいいですか？

関数の頭書きと、最後の return 文を省略しないでください。

コード:

int input_data(int a[N])  // データの入力
{
    int i;
    char buf[256];
    printf("\nEnter %d binary digits\n", N);
    printf("%.*s\n", N, "123456789.123456789.123456789.12");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i == N;  // i が N だったら 1 を、そうでなかったら 0 を返す
}

char buf[256]; は、行入力のためのバッファです。#define N 10 ですから、
10個の '0' と '1'、改行コードの '\n'、文字列の終わりの '\0' を入れるため
に最低 12個の char の領域が必要です。
N はもう少し大きくできますし、ユーザが間違って余計な文字を入れてしまうかも
しれないので、かなり大きめに 256個にしました。

次の printf は、Enter 10 binary digits と表示します。
その次の printfは、"123456789.123456789.123456789.12"という文字列の_うち
先頭の N 個、すなわち 10個を表示します。

fgets は、行入力関数です。標準入力 stdin(今はキーボード)から 1行分の
文字列を buf に読み込みます。
ユーザが Linux で Ctrl-D、Windows で Ctrl-Z を入力すると、それは入力終了の
意味になるので、fgets は読込みに失敗し、NULL を返します。
fgets() の前の単項演算子 ! はそれを検出して、演算結果を 1 にします。
if (1) になるので、return 0; が実行され、input_data()関数は呼び出し元に
0 を返します。これは、データが読み込めなかったという合図です。
通常は、ユーザが 0011010111 Enter などと入力するので、fgets() は成功し、
NULL 以外の値を返すので、! による演算結果が 0 になり、if (0) ですから
return 文は実行されません。buf には入力文字列が入っています。

その buf の先頭から N個の文字を、for文で順番に見ていき、
'1' だったら数値の 1 を、
'0' だったら数値の 0 を a に代入します。
'1' と '0' 以外の文字があったら、break; で forループを中断します。

最後の return文の意味はコメント通りです。
これで、main() の int a[N]; にデータの入力完了です。

さて、main() の while (input_data(a)) { ですが、正しく入力できた場合、
input_data() が 1 を返すので、while (1) { となり、{ から } までの文が実行され、
その後、input_data(a) の呼び出しに戻ってきます。
入力の終了や入力エラーの場合、input_data(a) は 0 を返すので、
while (0) { となり、{ から } までの文は実行されずにその次の return 0; に進みます。
main() 終了します。

[かずま]

この部分のどこを変換したらbit数をかえれるのでしょうか？

#define N 10 のところだけです。
ただし、28 か 29までです。30はダメです。

[かずま]

コード:

 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;
 

まずこれがどうしても何故これb を法とする整数の合同における a の逆元が求まるのかが全く分からないです。

「拡張ユークリッド　互除法　逆元」でググってください。

[ライトニング]

ｗやｂの単体の意味は分かるのですが中で何が行われてるのかがよく分からないのがほとんどの状態です....
(long long)*rのlong longを以前に説明してもらいましたが
これにrをかけてるのは何故でしょうか？またなぜlong longなのでしょうか？

print_arrayがいまいちどういうものかピンとこないのですが( " w",w)とか　(" sum = %d\n", sum)のwやsumの手前の空白部分などが
よくわからないのですがこれは何を表示させてるのでしょうか？("%d",w）とかはだめなのでしょうか？

int*q int*rなどの*はintにｑをかけるという意味でしょうか？それとも只*qというのを宣言してるだけでしょうか？　

[みけCAT]

(long long)*rのlong longを以前に説明してもらいましたが
これにrをかけてるのは何故でしょうか？

long longにrを掛けるなどという意味の分からない処理はありません。
これはポインタrが指す先のデータ(int型)を読み取り、その値をlong long型に変換しているだけですね。

またなぜlong longなのでしょうか？

int型の値同士を掛け算するとオーバーフローしてundefined behaviorになってしまうリスクがありますが、
もしもlong long型のサイズがint型の2倍であれば、int型の範囲の値をlong longにして掛け算をすることでオーバーフローを回避できるからでしょう。

( " w",w)とか　(" sum = %d\n", sum)のwやsumの手前の空白部分などが
よくわからないのですがこれは何を表示させてるのでしょうか？

文字列リテラル中の空白部分は、標準出力の内容を表示するアプリケーションに空白を表示させているのでしょう。
ソースコード中の文字列リテラル以外の空白部分は、ソースコードを編集するテキストエディタに空白を表示されているのでしょう。

("%d",w）とかはだめなのでしょうか？

No: 64のコードの５59行目のprint_array(" w", w);をprint_array("%d",w);にすることは、出力の意味がわかりにくくなるだけで問題はないでしょう。

int*q int*rなどの*はintにｑをかけるという意味でしょうか？

いいえ。

それとも只*qというのを宣言してるだけでしょうか？

いいえ。int*型(int型のデータを指すポインタ)の引数qやrを宣言しています。

オフトピック

C言語の文法的には「int*」と「q」ではなく「int」(declaration-specifiers)と「*q」(declarator)なんですけどね…

[かずま]

ｗやｂの単体の意味は分かるのですが中で何が行われてるのかがよく分からないのがほとんどの状態です....
(long long)*rのlong longを以前に説明してもらいましたが
これにrをかけてるのは何故でしょうか？またなぜlong longなのでしょうか？

*r は、main の r を参照するため、と説明したはずです。掛け算ではありません。

(long long) は #define N 20 のときに掛け算がオーバーフローしないようにするものです。
今は、#define N 10 ですから、不要です。削除してかまいません。

print_arrayがいまいちどういうものかピンとこないのですが( " w",w)とか　(" sum = %d\n", sum)のwやsumの手前の空白部分などが
よくわからないのですがこれは何を表示させてるのでしょうか？("%d",w）とかはだめなのでしょうか？

現在の表示は次の通り。

コード:

  w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
  sum = 6229
Private key
  w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
  q = 6233
  r = 3116
Public key
  b = [ 3114 3110 6219 6209 6185 6135 6038 2727 2338 1558 ]

Enter 10 binary digits
123456789.

w や sum の前の空白がないと、表示は次のようになります。ただそれだけのことです。

コード:

w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
sum = 6229
Private key
w = [ 5 13 28 48 96 196 390 779 1557 3117 ]
q = 6233
r = 3116
Public key
b = [ 3114 3110 6219 6209 6185 6135 6038 2727 2338 1558 ]

Enter 10 binary digits
123456789.

int*q int*rなどの*はintにｑをかけるという意味でしょうか？それとも只*qというのを宣言してるだけでしょうか？　

* はポインタです。
int *q は、q がポインタで、そのポインタは int を指しますよ。という意味です。
q は int ではありません。*q が int で、関数 generate_key() の呼出し元である main() の q を参照します。

鍵の生成を genearate_key() という別関数にしたため、混乱しているようですね。
では、関数にせず、main() に戻します。次のプログラムなら理解できますか？

コード:

#include <stdio.h>   // fgets, printf
#include <stdlib.h>  // rand, srand
#include <time.h>    // time
 
#define N  10
 
int gcd(int a, int b)    // 最大公約数
{
    int r;
    while (b)
        r = a % b, a = b, b = r;
    return a;
}
 
int inverse(int a, int b)  // b を法とする整数の合同における a の逆元
{
    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;
}

void print_array(const char *name, const int a[N]) // 配列の表示
{
    int i;
    printf("%s = [", name);
    for (i = 0; i < N; i++) printf(" %d", a[i]);
    printf(" ]\n");
}

int input_data(int a[N])  // データの入力
{
    int i;
    char buf[256];
    printf("\nEnter %d binary digits\n", N);
    printf("%.*s\n", N, "123456789.123456789.123456789.12");
    if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
        else break;
    return i == N;  // i が N だったら 1 を、そうでなかったら 0 を返す
}

int encrypt(const int a[N], const int b[N])  // 暗号化
{
    int i, c = 0;
    for (i = 0; i < N; i++)
        if (a[i] == 1) c += b[i];
    return c;
}

int decrypt(int c, const int w[N], int q, int r, int s[N])  // 復号
{
    int i, sum = c * inverse(r, q) % q;
    for (i = N; --i >= 0; ) {
        if (sum >= w[i])
            sum -= w[i], s[i] = 1;
        else
            s[i] = 0;
    }
    return sum; // 復号できれば 0、そうでなければ正の値を返す
}
 
int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ
    int i, sum = 0;
 
    srand(time(0));
 
    for (i = 0; i < N; i++)  // 超増加列(秘密鍵)の生成
        sum += w[i] = sum + 1 + rand() % 10;
    print_array("  w", w);
    printf("  sum = %d\n", sum);
    q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (r = q /2; gcd(r, q) != 1; ++r) ;  // 秘密鍵 r の生成
    for (i = 0; i < N; i++)  // 公開鍵の生成
        b[i] = r * w[i] % q;

    printf("Private key\n");
    print_array("  w", w);
    printf("  q = %d\n  r = %d\n", q, r);
    printf("Public key\n");
    print_array("  b", b);
 
    while (input_data(a)) {      // データの入力
        print_array("  a", a);   // 入力データの表示
        c = encrypt(a, b);       // 暗号化
        printf("  c = %d\n", c); // 暗号化されたデータの表示
        decrypt(c, w, q, r, s);  // 復号
        print_array("  s", s);   // 復号されたデータの表示
    }
    return 0;
}

さらに質問です。Wikipedia の 「Merkle-Hellmanナップサック暗号」は見ていますか？

[みけCAT]

オフトピック

* はポインタです。

確かにそうですね。

declarator:
[tab=30]pointer_opt direct-declarator

direct-declarator:
[tab=30]identifier
[tab=30](略)

pointer:
[tab=30]* type-qualifier-list_opt
[tab=30]* type-qualifier-list_opt pointer

(http://www.open-std.org/jtc1/sc22/wg14/ ... /n1256.pdf)

[ライトニング]

コード:

if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
 

この部分がまだいまいち理解できてないのですが (!fgets(buf, sizeof buf, stdin)) これが何か全く分からないです。
またbufは配列をいれる箱？なのは分かりますがbuf==1ならa=は１ってのは何故ですか？
aは秘密鍵の配列要素ですよね？

28行目のfor (i = 0; i < N; i++) printf(" %d", a);
ここでaを表示させるようにしてますが。aの計算はこれより後に計算してるのに何故先に表示するのを持ってきて実行できるのでしょうか？

ＭＨ暗号のWikiはみながら確認しています。

[かずま]

コード:

if (!fgets(buf, sizeof buf, stdin)) return 0;
    for (i = 0; i < N; i++)
        if (buf[i] == '1') a[i] = 1;
        else if (buf[i] == '0') a[i] = 0;
 

この部分がまだいまいち理解できてないのですが (!fgets(buf, sizeof buf, stdin)) これが何か全く分からないです。

No.105 に詳しく書いたのに分からないのですか？
No.105 の fgets() や ! の説明のどこが分からないのですか？

またbufは配列をいれる箱？なのは分かりますが

buf は文字列を入れる配列。
buf には、fgets() によりキーボードから文字列が入ります。
配列の各要素 buf には文字が入ります。

buf==1ならa=は１ってのは何故ですか？

buf == '1' です。
キーボードからの入力は文字列ですね。
buf には文字が入っています。
a には数値を入れなければなりません。
buf が文字の '1' なら a には数値の 1 を入れます。

aは秘密鍵の配列要素ですよね？

なんでそうなるの？ main() は無視ですか？

コード:

int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ

秘密鍵は b。
a は暗号する前のデータとはっきり書いてあります。
Wikipedia は無視ですか？
a は alpha、すなわち α。
b は beta、すなわち β。

28行目のfor (i = 0; i < N; i++) printf(" %d", a);
ここでaを表示させるようにしてますが。aの計算はこれより後に計算してるのに何故先に表示するのを持ってきて実行できるのでしょうか？

これは print_array() の中ですね。
ここの a は暗号化する前のデータではありません。
print_array(" w", w) で呼び出されたときは w。
print_array(" b", b) で呼び出されたときは b。
だから、まだ計算していない a や s ではありません。
関数の引数は、呼出し元の引数を引き継ぎます。

[かずま]

aは秘密鍵の配列要素ですよね？

なんでそうなるの？ main() は無視ですか？

コード:

int main(void)
{
    int w[N], q, r;  // 秘密鍵
    int b[N];        // 公開鍵
    int a[N];  // 暗号化する前のデータ
    int c;     // 暗号化されたデータ
    int s[N];  // 復号されたデータ

秘密鍵は b。
a は暗号する前のデータとはっきり書いてあります。
Wikipedia は無視ですか？
a は alpha、すなわち α。
b は beta、すなわち β。

すみません。
b は公開鍵でした。秘密鍵は w(と q と r)。
しかし、input_data(a) で呼び出された input_data() の中の a が、
暗号化する前のデータであることは確かです。
print_array() の中の a は、呼出しごとに変わります。

[ライトニング]

みけCATさんも分かり易い説明ありがとうございます。お二方の説明でだいたいは理解してきました。

あと１つ疑問なのですが

コード:

for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
 

かずまさんが説明してくださったこのfor分なのですがsum以上のqの値を決めるのはどの部分でしょうか？
またqの値を決めたらそれを２で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈でいいでしょうか？

[かずま]

コード:

for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;
 

かずまさんが説明してくださったこのfor分なのですがsum以上のqの値を決めるのはどの部分でしょうか？

そのひとつ上の行で、q の値を決めています。

No.86 のプログラム, 53行目 (generat_keys() の中から main() の q と r を参照するので、*q、*r )

コード:

    *q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (*r = *q /2; gcd(*r, *q) != 1; ++*r) ;  // 秘密鍵 r の生成

No.110 のプログラム, 81行目 (ここは main() の中なので q と r はそのまま)

コード:

    q = sum + 1 + rand() % 10;  // 秘密鍵 q の生成
    for (r = q /2; gcd(r, q) != 1; ++r) ;  // 秘密鍵 r の生成

またqの値を決めたらそれを２で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈でいいでしょうか？

No.103 の説明は読んでいないのですか？

[ライトニング]

そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。

この文はそういう意味じゃないのでしょうか？qを求め2/qを計算しそこからgdc(r, q) == 1 になるようなqを＋１増やしていき
gdc(r, q) == 1 になった時その値がrになるってことではないのでしょうか？
それとも2/qをした時点でその値がrになりそのrがgdc(r, q) == 1になるまで+1していくという事でしょうか？

[かずま]

まず、引用は、quoteタグを使うとか、行頭に > を付けるとかして、
引用と自分の文章との区別がつくように書いてください。

そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。

gdc は gcd の間違いでした。申し訳ありません。

> この文はそういう意味じゃないのでしょうか？

「この文」というのは、No.103 の文ですね。
「そういう意味」というのは、No.115 のライトニングさんの解釈でしょうか？

qの値を決めたらそれを２で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈

この解釈では、+1 してから、互いに素のチェックをしているようにも取れます。
それは間違い。互いに素であるかどうかのチェックが先です。

qを求め2/qを計算しそこからgdc(r, q) == 1 になるようなqを＋１増やしていき
gdc(r, q) == 1 になった時その値がrになるってことではないのでしょうか？

「2/q」は「q/2」の間違い。
「qを＋１増やしていき」は、「r を 1ずつ増やしていき」の間違い。

それとも2/qをした時点でその値がrになりそのrがgdc(r, q) == 1になるまで+1していくという事でしょうか？

「2/q」は「q/2」の間違いですが、「+1していく」が r のことなら、その通りです。
q/2 を計算した時点でそれを仮の r にしないと、gcd(r, q) != 1 のチェックができません。
最初から、gcd(r, q) == 1 なら、その r が決定した値です。
gcd(r, q) が 1 でなければ、r を 1 増やし、また gcd(r, q) のチェックに行きます。
そして、gcd(r, q) == 1 なら、求める r が決定します。

[Dixq (管理人)]

一つのトピックが長くなりすぎです。

１トピック１質問としてください。
また、トピックタイトルは質問内容が分かるように名前を付け、内容が変わったら新しくトピックを立ててください。
現在過去ログとして全く意味をなさないものになっています。

[かずま]

この続きは、Merkle-Hellmanナップサック暗号 で行います。
ここには、もう返信しないでください。