• 締切済み

3進展開による有限体上での累乗計算の方法

僕はペアリング暗号システムを作るために現在有限体上（標数3^97）の楕円曲線の計算プログラムを作成しています。その過程ででてくる数字で、a^((3^97+1)/4)という数字が出てきます。この指数を2進展開してdouble and add法を使って計算していたのですが、この方法だと少し計算速度が遅いのです。 そこで(3^97+1)/4という数字を3進数に直して演算を行えば高速化ができると思いました(標数が3の倍数になるから)が、その計算方法がわかりません。 double and add法のような形での計算方法が知りたいです。知っている方がいたら、是非教えてください。

回答 全件
a_n = (3^(2n+1)+1)/4 とおくと a_0 = 1 か…

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

a_n = (3^(2n+1)+1)/4 とおくと a_0 = 1 かつ a_(n+1) = 9 a_n - 2 です. だから, x = a からはじめて x = x^9 / a^2 を繰り返せばいい (x^9 = x^(2^3)×x なので, ここは double and add で計算) んだろうけど.... a^2 でわるところで, どのくらい性能が落るかはわかりません. 実用上は 1/a^2 を計算しておけばまし?

sal6195
質問者

お礼

回答ありがとうございます。 参考にさせていただきます＾＾ 考えてみたらこれはパソコンのカテゴリよりは数学のカテゴリで投稿するべき質問でしたね。 すみませんでした。

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • 楕円の円周の計算方法

    はじめまして。 さっそくですが、楕円の円周の計算方法を 教えていただけませんでしょうか？ 今仕事でボトルのデザインをやっているんですけど、 楕円のボトルの円周の正確な数字が出せなくて困っています。 お願いします。

  • 楕円曲線と乗除算の関係は？

    「いわば、楕円曲線という図形が計算機になる」と言われていますのは、如何なる意味に於いてでしょうか。　P※Q　で表されている演算と、乗除の関係は、如何なるものでしょうか。

  • エクセルの指数近似曲線の式の計算方法を教えてください

    分子量を求めるために作ったグラフに指数近似曲線を追加し、式を出したのですが、計算方法がわかりません。式はｙ＝１E＋13e＾－1.00855x(－1.00855ｘ乗ということを表しているつもりです)と出たのですが、どのようにして計算をすればよいのかわかりません。調べたところ、logを使って計算しているものもありましたが、数学が苦手で計算方法がよくわかりませんでした。logを使った方法でしたら、丁寧に計算の仕方まで書いていただけるとうれしいです。よろしくお願いします。

  • HHKBで数字計算をするときの操作方法は？

    HHKBで数字計算をするときの操作方法はどうされていますか？ Fnキーと「H」「J」「N」「M」に「*」「/」「+」「-」の四則演算記号がわりふられていますが、肝心の数字はFnキーなしの最上段ですよね。 「左手片手で数字をポチポチ押して、四則演算記号は左手で入力する方法で計算されているのでしょうか？結構、使いにくい方法なのでHHKBで行うスマートなやり方ってご存知ですか？ （テンキーを別途購入して使うとか、電卓の画面をマウスで押すとか、で回避されているのでしょうか？） ※OKWAVEより補足：「「ScanSnap/fiシリーズ/HHKB」商品について」についての質問です。

  • 浮動小数点数を10進表記するアルゴリズム

    与えられた浮動小数点数から正確な10進表記の文字列を得るにはどうすればよいでしょうか。 主に、2進の指数を10進の指数に直す部分で悩んでいます。 単純に考えれば、2進数字の各桁について10進表記の数字列を求めて10進演算する方法が思いつきますが、大きな数や小さな数では計算量が極端に増えてしまいます。もっと効率的な方法はないものでしょうか。 logを取ればうまいこと計算量を減らせそうな気もしますが、正確さが犠牲になりそうです。

  • 量子論の計算方法

    量子論の計算において離散量で有限の場合は行列表示、連続量をあつかう場合は積分を用いて計算します。しかし一次元調和振動子の場合などはシュレディンガー方程式を変数変換してエルミート多項式をとけばエネルギーが求まりますが、この場合は消滅生成演算子を用いてH=aa*＋1/2（無時限化しました）とおいてからa*を固有ベクトルにかけて計算すれば特殊関数を用いるよりもはるかに簡単にエネルギーを求めることができます。この方法は非常に便利なのですが、量子論のほかの計算（たとえば井戸型ポテンシャルや粒子の散乱等）には用いることができません。どうして調和振動子だけこの方法が適用できてほかのケースには当てはまらないのでしょうか。その理論的背景にはどのようなものがあるのでしょうか。わかる方がいらしたら教えてくれませんか。

  • 85の倍数と87の倍数を足して3000に近い数

    85の倍数と87の倍数を足して3000に一番近い数字を、簡単に出す計算方法というのはないでしょうか。 ひとつひとつ足していくのが一番早道なのかどうかを知りたく質問致しました。 ご回答どうか宜しくお願い致します。

  • ３の倍数と７進法

    ７進法についてです。 ある３の倍数を７進法に変換すると、４桁のぞろ目になった。このような性質をもつ数字は２つしか存在しないことを証明せよ。という問題で、計算していって７進数のときに３３３３と６６６６だということはわかりましたが、証明はどのようにすればよいのでしょうか？

  • modの計算方法について

    下記ホームページで紹介されているmodの計算方法について教えてください。 http://c4t.jp/introduction/cryptography/cryptography04.html (1)「素数」を法とする世界では、Xn mod 素数＝X という、元の数字と答え（X）が共に同じとなる「n」の値を「素数」から計算することができます。というのがありますが、例をあげて説明していただけないでしょうか？ (2)RSA暗号の概要で暗号分456はどのように計算するのでしょうか？ よろしくお願いします。

  • Java での指数表示（2.5E-4）を変換したい

    Java（android）にて電卓を作っております。 Double型の計算結果をString型に変換して表示させましたが、小さな数字は全て指数表示になります。2.5E-4　の表示を　0.00025　のString型に変換する方法は無いでしょうか？ Javaの仕様なので仕方がないのですが、方法を知っておられる方、教えてください。

AOMEIを使用したHDDからSSDへの換装について
このQ&Aのポイント
  • AOMEIを使用してHDDからSSDへの換装を考えています。クローンコピーにはデバイスの暗号化が必要で時間がかかり、トラブルのリスクもあります。そこで、AOMEIではHDDを外付けHDDにバックアップし、それをSSDに復元する方法を検討しています。
  • AOMEIの流れは次の通りです。まず、ブータブルメディアをUSBに作成し、SSDを初期化します。次に、パソコンのSSDを交換し、ブータブルメディアを起動して復元します。現在の状況を考慮して、この方法で換装することができるかどうかを知りたいです。
  • ご意見をいただけると幸いです。
回答を見る

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する