効率的な演算法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 09:26 UTC 版)
コンピュータ上で指数を自然数とする冪乗（累乗）を効率よく行う演算方法としてバイナリ法（二進数法; en:exponentiation by squaring) とも呼ばれる演算方法を示す。 RSA暗号や確率的素数判定法であるフェルマーテストなどでは、巨大な自然数を指数とする累乗を行う。この方法を使うと、指数がいかに巨大であっても高々そのビット数の2倍の回数の乗算で算出することが可能になり、繰り返し掛けるよりも大幅に効率がよくなる。特にRSA暗号やフェルマーテストなどにおいて各演算後に必要となる剰余演算（一般に最も計算時間がかかる）の回数を減らす効果がある。 一般に、コンピュータにとって標準的な（32ビットコンピュータならば約4億までの）自然数や浮動小数点数を底とする場合は下位桁から計算する方式を、前述のような巨大な自然数を底とする場合には上位桁から計算する方式を用いると効率が良い。
※この「効率的な演算法」の解説は、「冪乗」の解説の一部です。
「効率的な演算法」を含む「冪乗」の記事については、「冪乗」の概要を参照ください。
ウィキペディア小見出し辞書の「効率的な演算法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 効率的な演算法のページへのリンク
