mod計算?

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

mod計算?

#1

投稿記事 by 愛川 » 4年前

M = w-1C mod P w-1は wのまいなす一乗と言う意味です
この式でMを求めるプログラミングをCで作りたいのですが上手く想像ができないのですが何をつかえばいいかヒントをもらえないでしょうか?
ヒントをもらってから一度作ってみてまた投稿したいのでお願いしますm(__)m

box
記事: 1746
登録日時: 9年前

Re: mod計算?

#2

投稿記事 by box » 4年前

愛川 さんが書きました:M = w-1C mod P w-1は wのまいなす一乗と言う意味です
W-1C

C
とは何でしょうか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

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

Re: mod計算?

#3

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

ライセンス的に問題がなければ、The GNU MP Bignum Libraryを使うのが簡単でしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

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

Re: mod計算?

#4

投稿記事 by YuO » 4年前

剰余類環,というか剰余体上の話ですか?
オフトピック
じゃないとw-1とmod演算が同時に定義されない気がするのだけど。

愛川

Re: mod計算?

#5

投稿記事 by 愛川 » 4年前

https://ja.wikipedia.org/wiki/Merkle-He ... 7%E5%8F%B7
これの復号部分をC言語で作りたいという状況ですご指摘お願いしますm(_ _)m

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

Re: mod計算?

#6

投稿記事 by YuO » 4年前

やっぱり,整数の剰余類環上での話ですね。
オフトピック
Wikipediaの該当ページにおける変数の使用方法におけるq,rについて,互いに素が条件なのでqは素数である必要は無く,剰余体上の話とは限らない
であれば,w-1の説明は混乱を避けるために,wの-1乗ではなくwの(乗法の)逆元と書いてください。

で,互いに素な整数の乗法の逆元を求めるには,拡張ユークリッド互除法というものを使います。
まぁ,実際はwとqの組を求めるときにユークリッド互除法を使って調べて,その途中結果からw-1も求めておけばよいと思います。
そして,wは暗号にも復号にも使わないので,秘密鍵としてwのかわりにw-1を保持すれば十分だと思います。

高島

Re: mod計算?

#7

投稿記事 by 高島 » 4年前

なるほど...ユーグリッド互助法を使うプログラミング作ればいいのですね!ご指摘ありがとうございますm(_ _)m
何の関数を使うかとは教えていただけないでしょうか?

閉鎖

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