直截的手法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/11 10:07 UTC 版)
冪剰余を求める最も直截的な手法は、be を直接計算し、結果を m で割って余りを求める方法である。冪乗#効率的な演算法にあるように、冪乗の演算には、O(log(e)) 回の乗算が必要であり、それに加えて1回の剰余演算を施すことによって冪剰余を求めることができる。 例として、b = 4, e = 13, m = 497 の場合、c を計算することを考える。 c := 4 13 mod 497 {\displaystyle c:=4^{13}{\bmod {497}}} 413 は 67,108,864 であり、これを 497 で割ると、剰余の c は 445 であることがわかる。 b は1桁、e は2桁の数値だが、be は8桁にもなる。 強い暗号では、b は最低でも256桁の2進数（10進数では77桁）である。典型的な例として b = 5 × 1076 と e = 17 の場合を考えてみる。この場合、b は77桁であり、e は2桁だが、be は（10進で）1304桁にもなる。コンピュータにそのような計算をさせることはもちろん可能だが、性能は期待できない。b や e の桁数が増えるほど、be は扱いにくくなる。
※この「直截的手法」の解説は、「冪剰余」の解説の一部です。
「直截的手法」を含む「冪剰余」の記事については、「冪剰余」の概要を参照ください。
ウィキペディア小見出し辞書の「直截的手法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 直截的手法のページへのリンク
