Strona 1 z 1
-m^(-1) (mod 2^n)
: 26 lis 2005, o 00:08
autor: p!_trek
Chodzi mi o znalezienie szybkiego sposobu na obliczenie -m^(-1) (mod 2^b), gdzie gcd(m, b) = 1 Jest to 'stala' w algorytmie redukcji Montgomerego. Niestety znalezione przeze mnie wyjasnienie nie dociera do mnie.
-m^(-1) (mod 2^n)
: 29 lis 2005, o 09:24
autor: hes
Co rozumiesz przez "szybki sposób"?
Chcesz to szybko obliczyć na papierze? Wzór nie jest zbyt skomplikowany.
Program ma to szybko wykonać? Oblicz:
\(\displaystyle{ -\frac{1}{n}}\)
gdzie n=m AND maska
gdzie maska, składa się z jedynek na b+1 najmłodszych pozycjach i zer na pozostałych.
-m^(-1) (mod 2^n)
: 1 gru 2005, o 01:53
autor: p!_trek
Twoj sposob jest oczywisty, ale wymaga 'recznego' znalezienia elementu odwrotnego. Znalazlem taki algorytm opisany takim komentarzem:
XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
=> 2*X*A - X*X*A*A = 1
=> 2*(1) - (1) = 1
Niech b bedzie nieparzyste (jest to a dla powyzszego przykladu):
x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
x *= 2 - b * x; /* here x*a==1 mod 2**8 */
x *= 2 - b * x; /* here x*a==1 mod 2**16 */
x *= 2 - b * x; /* here x*a==1 mod 2**32 */
Jest to etap znajdowania elementu odwrotnego, dalej jest modulo 2^n (maski)