Tham gia Đăng nhập
Điểm:3
Darcy Sutton avatar Crypto

Độ phức tạp về thời gian của việc giải quyết DLog Khi biết g và P

lá cờ in
Darcy Sutton

Cái này (https://en.m.wikipedia.org/wiki/Discittle_logarithm) Bài viết Wikipedia làm tôi bối rối. Nếu bạn có phương trình a = g^n (mod P) và g, P và a đều đã biết, thì làm thế nào để một thuật toán giải nhanh cho n chạy trong thời gian hàm mũ, như bài viết này nêu. Nó không phải là tuyến tính hay tôi đang đọc sai bài viết này?

265
0 + 0
Điểm:6
DannyNiu avatar Crypto
lá cờ vu
DannyNiu

Nó tuyến tính với số lượng giá trị có thể có của $n$, có kích thước theo cấp số nhân với số bit được sử dụng để biểu diễn $n$ ở dạng nhị phân.

0 + 0
Darcy Sutton avatar
lá cờ in
Darcy Sutton
Ồ, tôi hiểu rồi. Cảm ơn sự giúp đỡ của bạn.
0
Hồi đáp
Điểm:4
kelalaka avatar Crypto
lá cờ in
kelalaka

Điều này là do quan niệm sai lầm phổ biến, đặc biệt là từ những người mới bắt đầu học độ phức tạp tính toán ; số phần tử hoặc số bit.

Trong độ phức tạp tính toán, độ phức tạp tính toán thường được biểu thị dưới dạng một hàm của kích thước $n$ (tính bằng bit) của đầu vào và độ phức tạp được biểu thị dưới dạng một hàm của $n$.

Bạn có thể cân nhắc đúng vì các thuật toán sắp xếp đang sử dụng số phần tử tuy nhiên bối cảnh là quan trọng; số lượng bit tự nhiên hơn trong mật mã vì chúng tôi đo lường bảo mật theo bit.

Do đó, kích thước đầu vào là hàm mũ trong đó đầu vào được đo bằng bit.

Nói rằng nó là tuyến tính trong khi xem xét số lượng giá trị có thể là sai lầm trong mật mã học vì cuối cùng bạn sẽ gặp khó khăn trong việc đồng ý với các nhà mật mã học. Do đó sử dụng số lượng bit.

0 + 0
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đă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.