Witam,
Mam pytanie odnośnie algorytmu RSA:
Jednym z jego kroków jest generowanie wartości funkcji Eulera dla n. Skąd wiemy, że możemy ją policzyć za pomocą wzoru:
\(\displaystyle{ \phi(n) = (p - 1) (q - 1)}\)
Pozdrawiam,
Algorytm RSA - funkcja Eulera
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Algorytm RSA - funkcja Eulera
Jeśli \(\displaystyle{ n= \prod_{i=1}^{m}p_i^{k_i}}\) jest rozkładem liczby \(\displaystyle{ n}\) na czynniki pierwsze, to:
\(\displaystyle{ \phi (n)= n\cdot \prod_{i=1}^{m}\left(1-\frac{1}{p_i} \right)=\prod_{i=1}^{m}\left(p_i^{k_i}-p_i^{k_i-1} \right)}\)
Q.
\(\displaystyle{ \phi (n)= n\cdot \prod_{i=1}^{m}\left(1-\frac{1}{p_i} \right)=\prod_{i=1}^{m}\left(p_i^{k_i}-p_i^{k_i-1} \right)}\)
Q.