(Được liệt kê chéo trên stackexchange toán học, không nhận được phản hồi nào)
Đối với ngữ cảnh, đây là một câu hỏi bài tập về nhà từ một bài tập đã được giao. Tôi đang tìm cách hiểu rõ hơn về các khái niệm liên quan, chủ yếu là lý thuyết phức tạp vì tôi chưa từng thấy nó trước đây bên ngoài lớp học này (và kiến thức trước đó đã được giả định).
Tôi được yêu cầu đánh giá độ phức tạp của quá trình giải mã RSA có và không sử dụng CRT, không sử dụng độ phức tạp tiệm cận. thay vì sử dụng $c_1$ là hằng số cho phép nhân mô-đun, $c_2$ cho lũy thừa mô-đun, và $c_3$ để tìm một nghịch đảo nhân.
Nỗ lực của tôi: Hãy để $s_1$ là chiều dài của $p$, $s_2$ là chiều dài của $q$, $s$ chiều dài của $n$, và $x$ chiều dài của $d$. Hãy xem xét các phức tạp sau:
| tính toán |
sự phức tạp |
| $m_1=c^d\mod p$ |
$c_2s_1^2x$ |
| $m_2=c^d\mod q$ |
$c_2s_2^2x$ |
| $q^{-1}\mod p$ |
$c_3s_1$ |
| $p^{-1}\mod q$ |
$c_3s_2$ |
Vì vậy, sự phức tạp của việc sử dụng CRT để tính toán $m=m_1(q^{-1}\mod p)q+m_2(p^{-1}\mod q)p\mod n$ Là $c_1^2c_2c_3s_1^3x+c_1^2c_2c_3s_2^3x=c_1^2c_2c_3x(s_1^3+s_2^3)$.
Trong khi đó, độ phức tạp để tính toán $m=c^d\mod n$ Là $c_2s^2x$, vì vậy sự khác biệt là $c_2x(s^2-c_1^2c_3(s_1^3+s_2^3))$.
Tôi tin rằng điều này là sai vì tôi không nghĩ nói chung là đúng $s^2\geq s_1^3+s_2^3$ (CRT sẽ giúp giải mã nhanh hơn) và tôi không biết liệu chúng ta có thể đưa ra bất kỳ giả định nào về các hằng số hay không.
