mody逆元計算

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

mody逆元計算

#1

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

コード:

#include <stdio.h>

int main(void)
{
    int x,y,z;
     z=10;  
   scanf("%d",&x);
   scanf("%d",&y);
   printf("%d\n",z*(x%y));
	return 0;
}
何度も質問失礼します。zにxmodyを掛けるのはこのような感じだと思うのですが、zにxmody^-1(yの逆元)を掛けるプログラミングは
どこを手直したら良いのでしょうか?

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

Re: mody逆元計算

#2

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

ライトニング さんが書きました:zにxmodyを掛けるのはこのような感じだと思うのですが、zにxmody^-1(yの逆元)を掛けるプログラミングは
どこを手直したら良いのでしょうか?
以下のようにしたら良いでしょう。
  1. main関数の前に「xmody^-1(yの逆元)」を計算する関数を定義する
  2. z*(x%y)をzにその関数の戻り値を掛ける式に変える
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

ライトニング

Re: mody逆元計算

#3

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

ご回答ありがとうございます。自分で色々調べたのですが逆元の計算のプログラミングが分からない状態です。
調べて拡張ユークリッドを使えばいいのかと思ったのですが最大公約数を求める事しかできずどう書けばいいか分からない状態です...

YuO
記事: 941
登録日時: 9年前
住所: 東京都世田谷区

Re: mody逆元計算

#4

投稿記事 by YuO » 4年前

yの逆元とあるのですが,yはどういう集合に含まれていて,どういう演算に対する逆元なのですか。
それがわからないと,逆元の計算自体が定義されないため,答えようがないと思うのですが。

ライトニング

Re: mody逆元計算

#5

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

例えば11mod5の逆元は11mod9になるような演算がしたい状態です!

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

Re: mody逆元計算

#6

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

ライトニング さんが書きました:例えば11mod5の逆元は11mod9になるような演算がしたい状態です!
1の逆元は2になるような演算がしたいということですか?
それとも「11mod5」や「11mod9」に何か一般的でない意味がありますか?
もし一般的でない意味があるのなら、それを説明してください。
逆元を求めるのに使う群(?)をきちんと定義していただけるとありがたいです。
(そもそもここで扱う「逆元」が群で定義される逆元であるとは限らないが…)
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

ライトニング

Re: mody逆元計算

#7

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

https://ja.wikipedia.org/wiki/Merkle-He ... 7%E5%8F%B7
これの復号部分の計算をしたい状況です。
r・qが素数でgcd(r,q) = 1ををえらび 
これのrの逆元を求めたい状態です。

かずま

Re: mody逆元計算

#8

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

コード:

#include <stdio.h>

int getInverse(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;
        x1 -= q * x2,  y1 -= q * y2,  z1 -= q * z2;
        #define SWAP(a, b)  (t = a, a = b, b = t)
        SWAP(x1, x2),  SWAP(y1, y2),  SWAP(z1, z2);
    }
    return x2 < 0 ? x2 + b : x2;
}

int main(void)
{
    int r, q;
    while (printf(">> "), scanf("%d%d", &r, &q) == 2)
        printf(" inverse(%d) = %d (mod %d)\n",
                r, getInverse(r, q), q);
    return 0;
}
実行結果

コード:

>> 3 7
 inverse(3) = 5 (mod 7)
>> 11 5
 inverse(11) = 1 (mod 5)
>> 11 9
 inverse(11) = 5 (mod 9)
>> .
逆元とは、掛け算をして結果が 1 (単位元) になるもの。
実数の場合は、逆数。
行列の場合は、逆行列。掛け算の結果は単位行列。
mod q の整数の合同の場合は、q で割った余りが等しいものは合同なので
掛け算の結果が 1 と合同であればよい。

コード:

   3 x 5 = 15 ≡ 8 ≡ 1 (mod 7)
  11 x 1 = 11 ≡ 6 ≡ 1 (mod 5)
  11 x 5 = 55 ≡ 46 ≡ 37 ≡ 28 ≡ 19 ≡ 10 ≡ 1 (mod 9)
int だと符号を除くと 31ビットしかないので、
暗号に使うのなら、多倍長計算が必要でしょう。

かずま

Re: mody逆元計算

#9

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

ライトニング さんが書きました:https://ja.wikipedia.org/wiki/Merkle-He ... 7%E5%8F%B7
これの復号部分の計算をしたい状況です。
r・qが素数でgcd(r,q) = 1ををえらび 
これのrの逆元を求めたい状態です。
その Wikipedia には、「またrはqと互いに素な整数でなければならない。
これは復号時にrの逆元を使うためである。」と書かれています。
「互いに素」と「素数」は、意味が違います。
例えば、15 は素数ではないけれど、15 と 7 は互いに素です。
共通の約数が 1 しかないことを互いに素といいます。

ライトニング

Re: mody逆元計算

#10

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

ご回答ありがとうございます。
自分の計算だと11mod5 5y ≡ 1(mod 11)となるyを求めよ、という意味で。
この場合なら逆元は9になるので 11mod5の逆元は9になるのですが
このプログラミングだと1と表示されるのですがどうすれば良いのでしょうか?

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

Re: mody逆元計算

#11

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

ライトニング さんが書きました:このプログラミングだと1と表示されるのですがどうすれば良いのでしょうか?
正しい入力を与えれば良いでしょう。
https://ideone.com/r17UIx
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

YuO
記事: 941
登録日時: 9年前
住所: 東京都世田谷区

Re: mody逆元計算

#12

投稿記事 by YuO » 4年前

気になっていたのと,それが障害になっているように感じたので。


表現 X mod Y とあった場合,どうもライトニングさんは「YをXで割った余り」というように使っているようですが,通常,「XをYで割った余り」という意味で使います。
合同式で expr1 ≡ expr2 (mod X) とあれば,「Xを法としてexpr1とexpr2は合同」,つまりexpr1をXで割った余りとexpr2をXで割った余りは等しい,という意味です。

11mod5と書かれている場合,通常の感覚では11を5で割った余りですから1に等しく,これはの乗法単位元ですから,乗法における逆元は1になります。
5 mod 11であれば,5に等しいので,11を法とする剰余類環上での乗法の逆元は9となります (5 * 9 = 45 = 4 * 11 + 1)。

modの左右を逆に捉えてしまうと,当然全ての式の読み方を間違うので,そこが問題なのでは,と思った次第です。

ライトニング

Re: mody逆元計算

#13

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

なるほど自分の説明が少し悪かったですね。申し訳ないです。ご回答ありがとうございます。

コード:

 
#include <stdio.h>
 
int getInverse(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;
        x1 -= q * x2,  y1 -= q * y2,  z1 -= q * z2;
        #define SWAP(a, b)  (t = a, a = b, b = t)
        SWAP(x1, x2),  SWAP(y1, y2),  SWAP(z1, z2);
    }
    return x2 < 0 ? x2 + b : x2;
}
 
int main(void)
{
    int r, q,z;
    while (printf(">> "), scanf("%d%d", &r, &q) == 2)
        printf(" inverse(%d) = %d (mod %d)\n",
                r, getInverse(r, q), q);
        printf("%d",z*r,q);
    return 0;
}
 

またこの出てきた逆元を何かにかけあわせるにはどうしたらよいでしょうか?
とりあえず変数zにかけようとしてみたのですがうまくいかなくて....

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

Re: mody逆元計算

#14

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

ライトニング さんが書きました:またこの出てきた逆元を何かにかけあわせるにはどうしたらよいでしょうか?
この出てきた逆元を何かにかけあわせるプログラムを書いてコンパイルして実行すればいいです。
ライトニング さんが書きました:とりあえず変数zにかけようとしてみたのですがうまくいかなくて....
zは初期化されていない自動変数なので、値は不定です。
また、rは逆元ではありません。逆元はgetInverse関数で求められそうです。
オフトピック
printfの書式に対して引数が多すぎても、無視されるだけで無害?
N1256 7.19.6.1 The fprintf function さんが書きました: If the format is exhausted while arguments remain, the excess arguments are
evaluated (as always) but are otherwise ignored.
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

ライトニング

Re: mody逆元計算

#15

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

ありがとうございました。参考にさせて頂きます。

閉鎖

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