-m^(-1) (mod 2^n)
-m^(-1) (mod 2^n)
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)
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.
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)
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)
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)