|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 乗算 ： [じょうざん] (n) multiplication
モンゴメリ乗算（モンゴメリじょうざん）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加減算・シフト演算のみで、高速に整数の積の剰余を求めることのできるアルゴリズムである。 数100ビットを超える法による冪剰余演算は、暗号理論の分野で重要な応用を持ち、モンゴメリ乗算を用いればこれを効率的に計算することができる。 Peter Montgomeryにより提案された。モンゴメリ法ともいう。 ==概要== モンゴメリ乗算のアイデアは、 を法とした合同算術に関して、演算したい値を、ある定数 を掛けた表現（ここではモンゴメリ表現と呼んでおく）に変換し、この表現によってすべての計算を行った後、最後に元の領域での表現に逆変換することである。 モンゴメリ表現での加減算はそのまま実行した後、負または 以上のときのみ の加減をするだけでよい。 しかし乗算では が余分に残るので、 を掛けて による剰余を求める処理を行う必要がある。 この処理をモンゴメリリダクションといい、 をうまく選ぶことにより効率的に計算することができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「モンゴメリ乗算」の詳細全文を読む スポンサード リンク
|