Chúng tôi sẽ sử dụng rất nhiều thực tế sau: đối với một mô đun công cố định $n$ tích của các số nguyên tố khác nhau, một cặp số nguyên $(e,d)$ tạo thành một cặp số mũ RSA phù hợp [nghĩa là với $c\mapsto c^d\bmod n\,=\,m$ có khả năng giải mã đáng tin cậy bất kỳ bản rõ nào $m$ Trong $[0,n)$ được mã hóa cho mỗi $m\mapsto m^e\bmod n\,=\,c$ ] nếu và chỉ nếu$$e\cdot d\equiv1\pmod{\lambda(n)}$$ở đâu $\lambda$ là chức năng carmichael. Điều đó có thể được chứng minh là tuân theo định nghĩa của $\lambda(n)$ là số nguyên dương nhỏ nhất $y$ như vậy mà $m^y\equiv 1\pmod n$ cho tất cả $m\in\mathbb Z^*$. Điều này giữ bất kể dấu hiệu của $d$.
Nó sau đó $t$ của bước 1 của thuật toán của câu hỏi là tồn tại $k\in \mathbb Z$ với $t=k\cdot\lambda(n)$.
Nếu thuật toán tìm thấy $f=1$ ở lần thực hiện đầu tiên của bước 2, do đó, nó giữ $r\cdot k\cdot\lambda(n)+s\cdot e_1=1$, vì thế $s\cdot e_1=1+(-r\cdot k)\cdot \lambda(n)$, do đó khi thuật toán đặt $d'_1=s$ ở bước 3 nó giữ $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$. Áp dụng thực tế đầu tiên, $(e_1,d'_1)$ là một cặp số mũ RSA phù hợp cho mô đun công khai $n$. Nếu chúng tôi muốn $d'_1$ để không tiêu cực chúng ta có thể làm cho $d'_1=s\bmod t$, mà theo định nghĩa là trong phạm vi $[0,t)$ và cũng như vậy $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$.
Mọi thứ trở nên sai lầm khi $f\ne1$ ở lần thực hiện đầu tiên của bước 2. Thường $s$ sẽ không chia $t$ ở bước 4, ngăn chặn việc áp dụng thuật toán như hiện tại. Ví dụ: $p=13$, $q=19$, $n=247$, $\varphi(n)=216$, $\lambda(n)=36$, $e_1=91$, $e_2=25$, $d_1=19$, $d_2=121$, $t=3024$, $r=-4$, $s=133$, $f=7$, $t/s=432/19\not\in\mathbb Z$.
Thay đổi $t:=\frac t s$ đến $t:=\frac t f$ ở bước 4 đảm bảo tính chia hết và để thuật toán hoạt động. Tranh luận: $f$ phân chia $e_1$, và $\gcd(e_1,\lambda(n))=1$, do đó $f$ là nguyên tố cùng với $\lambda(n)$, do đó chúng tôi khởi động lại bước 2 với $t$ vẫn là bội số của $\lambda(n)$.
Ngoài ra: đưa ra $(n,e_2,d_2)$ đối thủ có thể yếu tố $n$ (xem cái này) và từ đó nhận được $\hat{d_1}=e^{-1}\bmod\lambda(n)$ phù hợp $(n,e_1)$, thông thường với $\hat{d_1}$ nhỏ hơn/nhanh hơn $d'_1$; hoặc nhận khóa riêng đang hoạt động ở dạng cho phép vận hành màn hình CRT do đó giải mã hoặc chữ ký thậm chí còn nhanh hơn.
