• 締切済み

多倍長演算での累乗

ElGamal暗号のプログラムをjavaで書いているのですが、累乗の計算で困っています。 RSA暗号で出てくる「a^b mod p」の場合はBigIntegerを使うと「a.modPow(b,p)」ですよね。 しかし今回使う式は「a*(b^p-x-1) mod p」といったような式です。 ということで a.miltiply.b.pow(p.subtract(x).subtract(x)).mod(p) としたんですが、コンパイルしてエラーが出たので調べたところ、指数部分はint型でないとpow()が使えないことを知りました。 しかし、この式の指数部分が1024ビットなので32ビットのint型には変換できません。 int型以外の値で累乗するにはどうしたらいいのでしょうか？

  • ura10
  • お礼率58% (10/17)
  • Java
  • 回答数2
  • ありがとう数0

みんなの回答

  • rinkun
  • ベストアンサー率44% (706/1571)
回答No.2

まず、なぜpowの引数がint型なのかを考えましょう。 1024ビットで表現される数だけ累乗するとどれほどの大きさの数になるか考えればint型以外の値で累乗するのが現実的ではないことが分かります。 正しい方針は計算式を適当に変形してmodPowを使えるようにすることです。 modと四則演算の基本的な関係式で質問の式をmodPowを使う形に変換できるはずです。 # 具体的な変形は公式を覚えてないので省略

回答No.1

int型以外の値で累乗するプログラムを作る。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. Java

関連するQ&A

  • フェルマーの小定理

    RSAの勉強をしています。そこで質問なんですが p,qは異なる素数で a^b≡x (mod p) a^b≡x (mod q) のとき、 a^b≡x (mod p*q)になるのは明らかなんでしょうか。

  • 累乗　累乗根　同値性　その2

    累乗と累乗根の同値性について前回質問させて頂きました。 前回の質問内容：http://okwave.jp/qa/q7768635.html 前回、ご回答頂いた内容で、 ＞指数を実数の範囲にして同値性を保ちたいなら、 ＞x,y を正数だけに制限しておくのが安全です。 と教えて頂きました。 y=x^pにおいて無理数乗や、無理数乗根を考える場合はx,yは正数とすれば 同値性は保たれる理由はどうしてでしょうか？ 指数が偶数の場合に、同値性が崩れると理解しています。 無理数は偶数ではないから、同値性が崩れることはないと考えているのですが そんなに単純ではないのでしょうか？ x,yが正数でない場合（x,yが負の数）は同値性は保たれないのでしょうか？ 以上、ご回答よろしくお願い致します。

  • 累乗根と指数

    お恥ずかしいことですが、指数や累乗根の辺りがまったく分かりません。急に学ぶことになったのですが、ついていけません・・・。 どなたか、分数乗の扱い方についてご存知の方いらっしゃいますか？ （３＾√－１３３１）（Ｘ＾２/９）＾－３（１/Ｘ＾－１/３） 　↑立方根　　　　　　　　　　　　　　　　　　　↑－１/３乗 という式の場合、一体どのように手をつけていいのか。 また、 （Ｘ＾１/３・Ｙ＾１/２）＾－２ などの場合はどのようにしたらいいでしょうか？ どなたか回答よろしくお願いいたします。

  • 累乗→Logの式変形　

    累乗→Logの式変形　 累乗の指数が整数でなく計算出来ない場合はlogを使って値を出す方法があったと思うんですがやり方を忘れてしまいました。 下記の式なのですがどのように変形してどのように値を出すのかご教授願えませんでしょうか A' = A × (1/2)^4.5 loge2=3.2 2^4.5=24 ちなみに2^4.5などの値は今適当に書いたので違っていると思います。 よろしくお願いしますm(_ _)m

  • 指数関数　と　累乗根（無理関数）

    こんにちは。指数関数に関する質問です。 「ａを１でない正の定数とするとき、Ｙ＝ａ^xを、ａを底とする指数関数という。」という定義が本に記載されていました。そこで質問ですが、Ｙ＝Ｘ^aの場合は累乗根[←数II]（又は無理関数[←数III]）という名前がついているようですが、これは指数関数に含まれないのでしょうか？ ※質問は、指数関数と無理関数（又は累乗根）との関連です。 　別ものなのでしょうか、それとも包含関係があるのでしょうか？ よろしくお願いします。

  • Objective-Cで累乗根

    X÷Y（X/Y）のn累乗根に絡んだ計算をプログラミングをしようと下記のようにプログラムしたのですが、結果が０となりうまくいきません。アドバイスでも良いので、ご回答お願い致します。 float Z = pow(X / Y, 1 / n) -1*100; //計算結果 NSString *ZStr = [ NSString stringWithFormat: @"%f", Z ]; //計算結果書き出し P.text = [NSString stringWithFormat:@"%.3f",Z];

  • 公開鍵暗号方式の復号に関して質問します。

    暗号方式は、発信者Aさんが正当な受信者Bさんに暗号化した電文を送付し、途中で不正に傍受したCさんには電文の復号ができず、正当な受信者Bさんには復号ができるという考えかたです。 正当なる受信者Bさんには復号が可能で、不正なる傍受者Cさんには復号が不可能であるためには、BさんとCさんの間に情報格差を維持しないと駄目だと思うのですが、公開鍵方式の場合に正当なる受信者Bさんと不正な傍受者Cさんの間にどのような情報格差が存在するのでしょうか。 ＝＝＝　RSA暗号の例題を考えます ＝＝＝ A：暗号の発信者 B:正当なる暗号の受信者 C:不正なる暗号傍受者 Aさんは 素数P=3 素数Q=11 を選んで、 33を法とする世界（Mod33）を利用します。 Aさんは原文を3乗し、Mod33を取った暗号文をBさんに送付しますが、ここで、公開鍵情報として、「33を法とする」および「3乗した」という二つの情報を開示して暗号を送付します。 暗号を不正に傍受したCさんは、33の素因数分解ができないために、P=3、Q=11という二つの素数を特定できず、3xD=｛nｘ（p-1｝X(Q-1)+1｝において、N=1の場合でもP,Qが分からないので、復号することがきません。 ところが正当なる受信者Bさんは、3xD=1x（3-1）ｘ（11-1）+1=21より、D=7を求め、受診した暗号を7乗することで受信電文の復号が可能となります。 　＝＝＝＝　以上例題おわり　＝＝＝＝ 不正なる傍受者Cさんは素因数分解が困難であることから二つの素数P、Qの特定ができずに復号ができないことは良く理解できます。 しかし、正当なる受信者Bさんは、なぜP,Qを特定し、D=7を求めることが出来るのでしょうか。 質問１：なぜBさんだけが復号可能なのでしょうか？ 質問2：Bさんは素因数分解をせずとも、P=3、Q=11という二つの素数を知ることができるのでしょうか？ 質問3：素数P、Qの値を特定できなくてもD=7を知ることができるのでしょうか？ 公開鍵暗号方式の根本原理が分かっていないと思われるので、公開鍵暗号方式、あるいはRSA暗号方式の考え方をご存じの方ご教示いただけると助かります。

  • 最小二乗法の関数を四則演算と累乗だけで表す

    (x,y)=(a,b)、(c,d)、(e,f)、(g,h)、(i,j) という測定結果が与えられていて、 http://atsugi5761455.fc2web.com/calking4/c4_020.gif の行列からa_1～a_4の値を計算し、 http://atsugi5761455.fc2web.com/calking4/c4_013.gif の式にそれらを代入しP(x)の式を完成させたいのですが、 完成したP(x)の式を「+」「-」「*」「/」「^」だけの演算子でどうにか表せないでしょうか？ 途中までやってみたのですが50％くらいのところで挫折してしまいました・・・。 かなり長い式になると思います。 分かる方いらっしゃいましたら、大変恐縮ですがご回答の方よろしくお願い致します。

  • エクセルで累乗の回帰

    お世話様です。 エクセルのグラフで近似曲線の中に累乗というのがあります。 近似曲線式を書かすような設定にすると、 ｙ＝Aｘ^B（ｙイコールAかけるｘのB乗）ってでますよね。 このAとかBを数値として使いたいのですが、グラフの式から読み取っていちいち任意のセルにAとBを入力する手間を省きたいと思ってます。 マクロで式のテキストを読み取って文字列操作をそて数値を取得する、なんてことも考えましたが、それは自力でできそうかも、なので他の方法をご教授ください。 １）例えば、直線回帰ならLINEST関数がありますが、これみたいな関数があるのでしょうか？ ２）数学的（統計学的？）な知識でワークシートを駆使してできるのでしょうか？統計学的知識は大昔のことで忘れてしまったし参考書もありません。 どうかよろしくお願いします。

  • 構造体のメンバ変数が途中で変化してしまう

    下にあるプログラムでコメントが書いてある部分の"Tmp->x"の値が途中で期待していない変化をします。何回も見ても特に操作していないと見てしまいますが、構造体変数の扱い方がおかしいのでしょうか？ struct zahyo *MpCalculate(struct zahyo *P,int a,int multiple,int prime) { struct zahyo *kp,*Tmp; int i,u,r; kp=(struct zahyo*)malloc(sizeof(struct zahyo)); kp->x=P->x; kp->y=P->y; if(multiple == 1) return kp; u=myu(P,a,prime); kp->x=x3_PequalQ(P->x,u,prime); kp->y=y3(P,kp,u,prime); if(multiple == 2) return kp; printf("2Py(%d,%d)\n",kp->x,kp->y); //P≠Q for(i=3; i<=multiple; i++){ /*Tmp->xを表示させているDの部分で値が期待しない変化をします*/ Tmp=kp; A: printf("A:Tmp->x=%d\n",Tmp->x); r=rmd(Tmp,P,prime); B: printf("B:Tmp->x=%d\n",Tmp->x); kp->x=x3_PnotQ(Tmp,P,r,prime); D: printf("D:Tmp->x=%d\n",Tmp->x); kp->y=y3(Tmp,kp,r,prime); printf("%dPy(%d,%d)\n",i,kp->x,kp->y); } return kp; } int rmd(struct zahyo *P,struct zahyo *Q,int prime) { unsigned int m,n; m=mod(Q->x - P->x,prime); n=mod(Q->y - P->y,prime); exeuclid(m,prime,1,0,0,1); return mod(aa*n,prime); } int x3_PnotQ(struct zahyo *P,struct zahyo *Q,int rmd,int p) { /*ここでもTmp->x(P->x)の値は操作されていません*/ C:printf("C:Tmp->x = %d\n",P->x); return mod((int)pow(rmd,2) - P->x - Q->x,p); } 実行結果 A:Tmp->x=10 B:Tmp->x=10 C:Tmp->x=10 D:Tmp->x=5 常にDの部分で変わってしまいます。 このように変化する原因が分かる方、回答よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する