Điểm:6

Tại sao chúng ta không thể sử dụng chức năng Zeta để tìm kiếm các thừa số nguyên tố trong RSA?

lá cờ cn

Có thể tôi đã nhầm, nhưng nếu hàm Zeta hiệu quả để tính toán và đảo ngược, và nếu giả định của Riemann là đúng (có vẻ như vậy), thì chúng ta không thể sử dụng hàm Zeta để tìm các thừa số nguyên tố của các số lớn và tìm riêng một cách hiệu quả khóa của khóa RSA công khai?

kelalaka avatar
lá cờ in
Chào mừng bạn đến với Cryptography.se. Bạn có ý nghĩa gì khi _hiệu quả để tính toán và đảo ngược_?
stimulate avatar
lá cờ cn
@kelalaka hiệu quả để tính toán: về cơ bản có thể tính toán trong thời gian ngắn hơn theo cấp số nhân tương ứng với số nguyên tố mà chúng tôi đang tìm kiếm; đảo ngược: hiệu quả để tìm đầu vào zeta cho một số nguyên tố nhất định.
Điểm:11
lá cờ ru

Thứ nhất, tôi không nghĩ rằng $\zeta(s)$ là hiệu quả để tính toán. Mối quan tâm của chúng tôi trong việc tính toán $\zeta(s)$ cho các mục đích lý thuyết số nguyên tố thường tập trung vào đường tới hạn $\mathrm{Re}s=1/2$Công thức Riemann-Siegel đòi hỏi $O(t^{1/2})$ thuật ngữ để tính toán $\zeta(1/2+nó)$. Có những cách tăng tốc để tính toán bội số giá trị, nhưng không đáng kể như vậy.

Tương tự như vậy, tôi không chắc ý của bạn là đảo ngược. Hàm này không phải là song ánh (chẳng hạn như chúng ta biết nhiều nơi nó bằng 0).

Điều đó nói rằng, đã có một số ý tưởng xung quanh việc sử dụng lý thuyết số giải tích cho các phương pháp bao thanh toán. Phương pháp phân tích nhóm lớp của Shanks có thể được tăng tốc nếu người ta có thể tính gần đúng $L(1,\chi_N)$ (ở đây $L$-hàm dành cho trường số $\mathbb Q(\sqrt N)$ và có liên quan mật thiết với $\zeta(s)$. Giả sử giả thuyết Riemann tổng quát hóa, Shanks đã cố gắng giảm thời gian chạy thuật toán của mình thành yếu tố $N$ từ $O(N^{1/4+\epsilon})$ đến $O(N^{1/5+\epsilon})$. Độ phức tạp như vậy không có khả năng ảnh hưởng đến các số lớn hơn vài trăm bit và không thể cạnh tranh với sàng trường số chung.

Đã có ý tưởng sử dụng $\zeta(s)$ chính nó (xem bài báo gần đây "Bao thanh toán với gợi ý" của Sica chẳng hạn), nhưng những bài báo này gặp khó khăn trong việc tiếp cận sự phức tạp của các phương pháp của Shanks trong những năm 1970 (bài báo của Sica có độ phức tạp $O(N^{1/3+\epsilon})$.)

Điểm:4
lá cờ us

Chúng ta không thể sử dụng hàm Zeta để tìm các thừa số nguyên tố của các số lớn một cách hiệu quả và tìm các khóa riêng của các khóa RSA công khai

Tóm lại: Các $\zeta$ chức năng không cấp quyền truy cập vào các số nguyên tố riêng lẻ (Tôi không biết có công thức nào làm được điều đó), vì vậy ngay cả khi chúng ta có một phương pháp tính toán siêu nhanh, nó cũng không thể được sử dụng để tìm thấy số nguyên tố.


  • Cái gì $\zeta$ chức năng cấp quyền truy cập, ví dụ như con số của các số nguyên tố giữa $1$$x$, tức là hàm đếm số nguyên tố $\pi(x)$.

    Thực sự có một mối quan hệ giữa chức năng đếm số nguyên tố $\pi(x)$, và tất cả các số không $\rho$ của Riemann $\zeta$ chức năng:

    $$\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac 12}\ ln(1-x^{{-2}}).$$

    Ở đây nghĩ về $\psi_0(x)$ như một cái gì đó rất gần với $\pi(x)$ trong ý tưởng, nhưng nó chỉ đếm các số nguyên tố có trọng số khác $1$ cho mỗi số nguyên tố, thay vào đó trọng lượng là $\log p$. Đây là bỏ qua chi tiết, nhưng nó đưa ra ý tưởng. Nhìn thấy đây để biết thêm độ chính xác.

  • Tích Euler cho $\zeta$ chức năng liên quan đến tất cả các số nguyên tố, nhưng không đưa ra cách hiệu quả để tạo/tìm số nguyên tố:

    $$\zeta(s) = \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{ \frac {1}{1-p^{-s}}}$$

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.