格納

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ライトニング

Re: 格納

#101

投稿記事 by ライトニング » 8年前

コード:

 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数でもできるように新たなNTLでも動くようにと課題が与えられました。
これのNTLを使って実装の後にもまた別の最後の課題が与えられまずはこっちを理解しなければならない状態です。

かずま

Re: 格納

#102

投稿記事 by かずま » 8年前

ライトニング さんが書きました:

コード:

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 となっています。

つづく

かずま

Re: 格納

#103

投稿記事 by かずま » 8年前

かずま さんが書きました:つづく
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ずつ増やしていって、適切な値を求めています。

かずま

Re: 格納

#104

投稿記事 by かずま » 8年前

ライトニング さんが書きました:

コード:

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 で参照できるようになっています。

かずま

Re: 格納

#105

投稿記事 by かずま » 8年前

ライトニング さんが書きました: この部分は何をやってるかが全くわからない状態です。 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() 終了します。

かずま

Re: 格納

#106

投稿記事 by かずま » 8年前

ライトニング さんが書きました:この部分のどこを変換したらbit数をかえれるのでしょうか?
#define N 10 のところだけです。
ただし、28 か 29までです。30はダメです。

かずま

Re: 格納

#107

投稿記事 by かずま » 8年前

ライトニング さんが書きました:

コード:

 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 の逆元が求まるのかが全く分からないです。
「拡張ユークリッド 互除法 逆元」でググってください。

ライトニング

Re: 格納

#108

投稿記事 by ライトニング » 8年前

wやbの単体の意味は分かるのですが中で何が行われてるのかがよく分からないのがほとんどの状態です....
(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をかけるという意味でしょうか?それとも只*qというのを宣言してるだけでしょうか? 

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 格納

#109

投稿記事 by みけCAT » 8年前

ライトニング さんが書きました:(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のコードの559行目のprint_array(" w", w);をprint_array("%d",w);にすることは、出力の意味がわかりにくくなるだけで問題はないでしょう。
ライトニング さんが書きました:int*q int*rなどの*はintにqをかけるという意味でしょうか?
いいえ。
ライトニング さんが書きました:それとも只*qというのを宣言してるだけでしょうか?
いいえ。int*型(int型のデータを指すポインタ)の引数qやrを宣言しています。
オフトピック
C言語の文法的には「int*」と「q」ではなく「int」(declaration-specifiers)と「*q」(declarator)なんですけどね…
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

かずま

Re: 格納

#110

投稿記事 by かずま » 8年前

ライトニング さんが書きました:wやbの単体の意味は分かるのですが中で何が行われてるのかがよく分からないのがほとんどの状態です....
(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をかけるという意味でしょうか?それとも只*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
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 格納

#111

投稿記事 by みけCAT » 8年前

オフトピック
かずま さんが書きました:* はポインタです。
確かにそうですね。
N1256 6.7.5 Declarators さんが書きました: declarator:
[tab=30]pointeropt direct-declarator

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

pointer:
[tab=30]* type-qualifier-listopt
[tab=30]* type-qualifier-listopt pointer
(http://www.open-std.org/jtc1/sc22/wg14/ ... /n1256.pdf)
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

ライトニング

Re: 格納

#112

投稿記事 by ライトニング » 8年前

コード:

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=は1ってのは何故ですか?
aは秘密鍵の配列要素ですよね?

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

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

かずま

Re: 格納

#113

投稿記事 by かずま » 8年前

ライトニング さんが書きました:

コード:

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=は1ってのは何故ですか?

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 ではありません。
関数の引数は、呼出し元の引数を引き継ぎます。

かずま

Re: 格納

#114

投稿記事 by かずま » 8年前

かずま さんが書きました:
ライトニング さんが書きました: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 は、呼出しごとに変わります。

ライトニング

Re: 格納

#115

投稿記事 by ライトニング » 8年前

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

あと1つ疑問なのですが

コード:

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

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

かずま

Re: 格納

#116

投稿記事 by かずま » 8年前

ライトニング さんが書きました:

コード:

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の値を決めたらそれを2で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈でいいでしょうか?
No.103 の説明は読んでいないのですか?

ライトニング

Re: 格納

#117

投稿記事 by ライトニング » 8年前

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

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

かずま

Re: 格納

#118

投稿記事 by かずま » 8年前

まず、引用は、quoteタグを使うとか、行頭に > を付けるとかして、
引用と自分の文章との区別がつくように書いてください。
No.103 で、かずま さんが書きました: そこで、私は、r を q/2 と q の間と考え、q/2 にしました。
r は q と互いに素でなければなりませんから、gdc(r, q) == 1 になるまで、
r を 1ずつ増やしていって、適切な値を求めています。
gdc は gcd の間違いでした。申し訳ありません。

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

「この文」というのは、No.103 の文ですね。
「そういう意味」というのは、No.115 のライトニングさんの解釈でしょうか?
NO.115 で、ライトニング さんが書きました: qの値を決めたらそれを2で割りその値を+1ずつしていき最初のqの値と素になればその値がrとなるという解釈
この解釈では、+1 してから、互いに素のチェックをしているようにも取れます。
それは間違い。互いに素であるかどうかのチェックが先です。
NO.117 ライトニング さんが書きました: qを求め2/qを計算しそこからgdc(r, q) == 1 になるようなqを+1増やしていき
gdc(r, q) == 1 になった時その値がrになるってことではないのでしょうか?
「2/q」は「q/2」の間違い。
「qを+1増やしていき」は、「r を 1ずつ増やしていき」の間違い。
NO.117 ライトニング さんが書きました: それとも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 (管理人)
管理人
記事: 1661
登録日時: 13年前
住所: 北海道札幌市
連絡を取る:

Re: 格納

#119

投稿記事 by Dixq (管理人) » 8年前

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

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

かずま

Re: 格納

#120

投稿記事 by かずま » 8年前

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

閉鎖

“C言語何でも質問掲示板” へ戻る