Matematyka.pl

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 ...

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.

Czesc!

Potrzebuje dobrze opisanego algorytmu dzielenia multiprecyzyjnego (dzilajacego na wielu slowach maszynowych). Korzystam z ksiazki Handbook of Apllied Cryptography, ale tamten jest dla mnie niezrozumialy.

Oczywiscie blad, jakies zamroczenie mnie dopadlo. Sorki

[ Dodano: Pon Lis 14, 2005 10:58 am ]
Wydaj mi sie ze taraz jest dobrze:
\(\displaystyle{ 0 = (1 + (-1)) = (1 + (-1))a = a + (-1)a = 0}\)

z tego wynika ze \(\displaystyle{ (-1)a}\) jest elementem odwrotnym do \(\displaystyle{ a}\)

Niech \(\displaystyle{ a}\) i \(\displaystyle{ b}\) naleza do \(\displaystyle{ K}\), to:

\(\displaystyle{ ab = (a + 0)b = ab + 0b \Rightarrow 0b = 0\\
(-1)a = (0 - 1)a = 0a - a = -a}\)