mody逆元計算
Posted: 2015年10月29日(木) 17:31
以下のようにしたら良いでしょう。ライトニング さんが書きました:ｚにxmodyを掛けるのはこのような感じだと思うのですが、zにxmodｙ^-1（yの逆元)を掛けるプログラミングは
どこを手直したら良いのでしょうか？
- main関数の前に「xmodｙ^-1（yの逆元)」を計算する関数を定義する
- z*(x%y)をzにその関数の戻り値を掛ける式に変える
以下のようにしたら良いでしょう。ライトニング さんが書きました:ｚにxmodyを掛けるのはこのような感じだと思うのですが、zにxmodｙ^-1（yの逆元)を掛けるプログラミングは
どこを手直したら良いのでしょうか？
1の逆元は2になるような演算がしたいということですか？ライトニング さんが書きました:例えば11mod5の逆元は11mod9になるような演算がしたい状態です！
#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)
>> .
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)
その Wikipedia には、「またrはqと互いに素な整数でなければならない。ライトニング さんが書きました: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,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は初期化されていない自動変数なので、値は不定です。ライトニング さんが書きました:とりあえず変数zにかけようとしてみたのですがうまくいかなくて....
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.