mody逆元計算

[ライトニング]

コード:

#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;
}

何度も質問失礼します。ｚにxmodyを掛けるのはこのような感じだと思うのですが、zにxmodｙ^-1（yの逆元)を掛けるプログラミングは
どこを手直したら良いのでしょうか？

[みけCAT]

ｚにxmodyを掛けるのはこのような感じだと思うのですが、zにxmodｙ^-1（yの逆元)を掛けるプログラミングは
どこを手直したら良いのでしょうか？

以下のようにしたら良いでしょう。

1. main関数の前に「xmodｙ^-1（yの逆元)」を計算する関数を定義する
2. z*(x%y)をzにその関数の戻り値を掛ける式に変える

[ライトニング]

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

[YuO]

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

[ライトニング]

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

[みけCAT]

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

1の逆元は2になるような演算がしたいということですか？
それとも「11mod5」や「11mod9」に何か一般的でない意味がありますか？
もし一般的でない意味があるのなら、それを説明してください。
逆元を求めるのに使う群(?)をきちんと定義していただけるとありがたいです。
(そもそもここで扱う「逆元」が群で定義される逆元であるとは限らないが…)

[ライトニング]

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

[かずま]

コード:

#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ビットしかないので、
暗号に使うのなら、多倍長計算が必要でしょう。

[かずま]

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

その Wikipedia には、「またrはqと互いに素な整数でなければならない。
これは復号時にrの逆元を使うためである。」と書かれています。
「互いに素」と「素数」は、意味が違います。
例えば、15 は素数ではないけれど、15 と 7 は互いに素です。
共通の約数が 1 しかないことを互いに素といいます。

[ライトニング]

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

[みけCAT]

このプログラミングだと1と表示されるのですがどうすれば良いのでしょうか？

正しい入力を与えれば良いでしょう。
https://ideone.com/r17UIx

[YuO]

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


表現 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の左右を逆に捉えてしまうと，当然全ての式の読み方を間違うので，そこが問題なのでは，と思った次第です。

[ライトニング]

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

コード:

 
#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]

またこの出てきた逆元を何かにかけあわせるにはどうしたらよいでしょうか？

この出てきた逆元を何かにかけあわせるプログラムを書いてコンパイルして実行すればいいです。

とりあえず変数zにかけようとしてみたのですがうまくいかなくて....

zは初期化されていない自動変数なので、値は不定です。
また、rは逆元ではありません。逆元はgetInverse関数で求められそうです。

オフトピック

printfの書式に対して引数が多すぎても、無視されるだけで無害？

If the format is exhausted while arguments remain, the excess arguments are
evaluated (as always) but are otherwise ignored.

[ライトニング]

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