Algorytm RSA - obliczanie współczynnika d

[Seahawk]

Mam problem z obliczeniem współczynnika d, który jest częścią klucza prywatnego (d, n) w algorytmie RSA. Potrafię bez problemu zaszyfrować tekst w RSA oraz zdeszyfrować, ale mam problem z obliczeniem współczynnika d.

Jest on obliczany ze wzoru \(\displaystyle{ d = e^-1 mod \phi(n)}\) za pomocą rozszerzonego algorytmu Eukulidesa.
\(\displaystyle{ \phi(n)}\) to funkcja Eulera czyli\(\displaystyle{ \phi(n) = (p-1)*(q-1)}\), p i q to liczby pierwsze, które wybiera się do obliczenia n i potem użycia do zaszyfrowania RSA i deszyfrowania.
e - to liczba względnie pierwsza z \(\displaystyle{ \phi(n)}\) czyli NWD(fi(n), e) = 1

Mam tylko problem z jego zastosowaniem do powyższego wzoru. Jeśli znacie jakiś sposób żeby obliczyć współczynnik d tym algorytmem to byłbym wdzięczny za odpowiedź.

[ksisquare]

wylosuj \(\displaystyle{ 1<e< \phi}\), sprawdź czy względnie pierwsze z \(\displaystyle{ \phi}\),
kiedy już takie znajdziesz policz \(\displaystyle{ d}\)

"In practice, common choices for \(\displaystyle{ e}\) are \(\displaystyle{ 3, 17}\) and \(\displaystyle{ 65537 (216+1)}\). These are Fermat primes, sometimes referred to as \(\displaystyle{ F_0, F_2}\) and \(\displaystyle{ F_4}\) respectively (\(\displaystyle{ F_x=2^{2^x}+1}\)). They are chosen because they make the modular exponentiation operation faster. Also, having chosen \(\displaystyle{ e}\), it is simpler to test whether \(\displaystyle{ \gcd(e, p-1)=1}\) and \(\displaystyle{ gcd(\e, q-1)=1}\) while generating and testing the primes in step \(\displaystyle{ 1}\). Values of \(\displaystyle{ p}\) or \(\displaystyle{ q}\) that fail this test can be rejected there and then. (Even better: if \(\displaystyle{ e}\) is prime and greater than \(\displaystyle{ 2}\) then you can do the less-expensive test \(\displaystyle{ (p \mod e) \neq 1}\) instead of \(\displaystyle{ \gcd(p-1,e)==1}\).)"