べき乗剰余計算アルゴリズム【バイナリー法】

[haku]

はじめまして☆
大学で情報セキュリティの研究室に属しています、hakuと申します。

情報セキュリティの研究室に属してはいますが、恥ずかしながら今までCをいじった経験はほとんどなく、研究の課題に苦しんでいます。

今取り組んでいるのはRSA暗号で使う、べき乗剰余計算アルゴリズムのバイナリー法をC言語で書くというものです。
以下は最も基本的なバイナリー法のアルゴリズムです。

【バイナリー法】
データのビット長をn, dのバイナリー（二進数）表現を(d[n-1],d[n-2],....d[0])とし、入力a,N,d,出力S=a^d mod Nとする。
[STEP1]S=1,j=n-1とおく。
[STEP2]j<0であればSを出力して終了し、j>=0であればSTEP3に進む。
[STEP3]S=(S*S) mod Nを計算し、STEP4へ。
[STEP4]d[j]=0のときはSTEP5に進む。d[j]=1であるときはS=(S*a) mod Nを計算し、STEP5へ。
[STEP5]j=j-1としてSTEP2に戻る。


私の研究では巨大な数のべき乗計算を扱うので、標準ライブラリ関数のpowではなく、どうしてもこのバイナリー法のアルゴリズムをC言語で書くことが必要になったのです。

自分でもやってみたのですが、10進数で与えたdの値を2進数に直したときに、STEP4の『d[j]=1であるときはS=(S*a) mod Nを計算し』というところをC言語でどのようにd[j]=1であるのか判定させ=(S*a) mod Nという計算にもっていくのか、というところがどうしてもできません。

例えば
S=3^21 mod 11のバイナリー法での計算を考えたときに、まずd=21を2進数に直すと、(10101)となりますがSTEP4に進んだときにd[j]=0なのかd[j]=1なのかをどう判定するのか、というところです。ちなみに2進数に直すときには配列を使って配列に1or0を入れていきました。

わかりにくい説明で申し訳ないのですが、よろしくお願いします。

一応、自分が考えている10進数から2進数に直すまでのプログラムを載せておきます。私はこれを使ってSTEP4のループのところを考えましたが、うまくできませんでした(>_<)

[Sleepy]

何やらゴチャゴチャ書いてありますが、
3^21 mod 11をC言語で計算したいのでやり方を教えて欲しい。
との質問でよろしいのでしょうか？

ただ研究の課題であるならご自分で研究なさるべきです。
安易に誰かの研究成果を寄せ集めるのはどうかと思います。

べつに完成しなくても研究の成果は、
C言語での巨大な数のべき乗計算の手法として、
ひとつの立派な研究として成り立つと思います。

[haku]

そうですね。わかりにくくてすいません(>_<)

最終的な課題というか、そこに行くまでの途中のところでして。。。
４人で分担してプログラムを書いてまして、一人がつまづくと他にも迷惑がかかるので焦ってたんです(；一_一)

[Sleepy]

ならばまず他の人に、
このままじゃできないどうしよう。
と相談すべきです。

4人で話し合えば何か解決策が見つかるかもです。

尚、プログラムは書く前に実現方法を明確にするものです。
実現方法も分からないままプログラムを書き始めると、
ほぼ間違いなく地獄に落ちることになります。

[haku]

それぞれの課題が大変そうだったのでなかなか聞きにくくて。。。でも聞いてみますね！

[box]

バイナリー法とどこまで関連するかはよくわからないですが、
べき乗数の剰余を求める際は「整数の合同」について
調べてみるとよいかもしれません。

[haku]

解決しました！
ありがとうございました！