Rが2の冪の時のN'の効率的な求め方
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 23:01 UTC 版)
「モンゴメリ乗算」の記事における「Rが2の冪の時のN'の効率的な求め方」の解説
Rが2の冪である場合には、計算機向けの効率的な求め方が存在する。 N N ′ ≡ − 1 ( mod R ) {\displaystyle NN'\equiv -1{\pmod {R}}} は N N ′ ≡ R − 1 ( mod R ) {\displaystyle NN'\equiv R-1{\pmod {R}}} であり、Rが2の冪であるためR-1は二進数表記で全てのビットが1になる。また2の冪での剰余を求めることは即ち二進数表記での下位ビットを取り出すことである。なのでこれは実質的に、NN'の二進数表記の下位ビット全てが1になるN'を求めることに相当する。 int result = 0;int t = 0;int r = R;int i = 1;while( r > 1 ) /* Rのトップビットを除いたビット数分繰り返す */{ if( !( t % 2 ) ) /* ゼロになっているビットがあったら、N'のその部分を1にする（NはRと互いに素なので必ず奇数） */ { t += N; /* 掛け算だが、二進数一桁の掛け算なので実質は足し算 */ result += i; /* N'のその部分を1にする */ } t /= 2; /* 必ず端数が出るが切り捨てる */ r /= 2; /* Rは2の冪なので、絶対端数は出ない */ i *= 2;}/* return result; この時点で N' == result */
※この「Rが2の冪の時のN'の効率的な求め方」の解説は、「モンゴメリ乗算」の解説の一部です。
「Rが2の冪の時のN'の効率的な求め方」を含む「モンゴメリ乗算」の記事については、「モンゴメリ乗算」の概要を参照ください。
- Rが2の冪の時のN'の効率的な求め方のページへのリンク
