tại sao hệ số nguyên là một thời gian không đa thức?

Question

Tôi chỉ là người mới bắt đầu khoa học máy tính. Tôi đã học được điều gì đó về thời gian chạy nhưng tôi không thể chắc chắn những gì tôi hiểu là đúng. Vì vậy, hãy giúp tôi.

Vì vậy, việc tích lũy số nguyên hiện không phải là vấn đề thời gian đa thức nhưng thử nghiệm nguyên thủy là. Giả sử số cần kiểm tra là n. Nếu chúng ta chạy một chương trình chỉ để quyết định xem mỗi số từ 1 đến sqrt (n) có thể chia n, và nếu câu trả lời là có, sau đó lưu trữ số. Tôi nghĩ rằng chương trình này là thời gian đa thức, phải không?

Một cách có thể là tôi sai sẽ là một chương trình nhân tố hóa nên tìm tất cả các số nguyên tố, thay vì nguyên tố đầu tiên được phát hiện. Vì vậy, có lẽ đây là lý do tại sao.

Tuy nhiên, trong mật mã khóa công khai, việc tìm kiếm hệ số nguyên tố của một số lớn là điều cần thiết để tấn công mật mã. Vì thường là một số lượng lớn (khóa công khai) chỉ là sản phẩm của hai số nguyên tố, việc tìm kiếm một số nguyên tố có nghĩa là tìm ra số nguyên tố kia. Đây nên là thời gian đa thức. Vậy tại sao nó khó khăn hoặc không thể tấn công?

Answer 1

Mô tả thông thường về sự phức tạp như "đa thức thừa thuật toán "thường đề cập đến độ phức tạp đối với kích thước của đầu vào, không phải là thông số giải thích của đầu vào. Vì vậy, khi mọi người nói "không có thuật toán bao thanh toán đa thức đã biết", nghĩa là không có thuật toán đã biết cho việc bao thanh toán số N-bit số tự nhiên chạy theo đa thức thời gian đối với N. Không đa thức đối với chính số đó, có thể lên đến 2^N.

Answer 2

Nếu chúng tôi chạy chương trình chỉ để quyết định xem mọi số từ 1 đến sqrt (n) có thể chia n và nếu câu trả lời là có thì hãy lưu số.

Thậm chí bỏ qua thử nghiệm chia sẽ mất nhiều thời gian hơn cho số lớn hơn, cách tiếp cận này mất gần gấp đôi nếu bạn chỉ thêm một số (nhị phân) vào n. (Trên thực tế, sẽ mất gấp đôi nếu bạn thêm hai chữ số)

Tôi nghĩ đó là định nghĩa về thời gian chạy theo hàm mũ: Làm cho một thời gian dài hơn, thuật toán mất gấp đôi thời gian.

Nhưng lưu ý rằng quan sát này chỉ áp dụng cho thuật toán bạn đã đề xuất. Nó vẫn còn chưa biết nếu hệ số nguyên số nguyên là đa thức hay không. Các nhà mã hóa chắc chắn hy vọng rằng nó không phải là, nhưng cũng có những thuật toán thay thế mà không phụ thuộc vào hệ số nguyên tố khó (như mã hóa đường cong elip), chỉ trong trường hợp ...

Answer 3

Khó khăn trong việc nhân tố hóa là một trong những vấn đề toán học tuyệt vời đơn giản để hiểu và đưa bạn ngay lập tức đến với kiến ​​thức của con người. Để tóm tắt kiến ​​thức (ngày nay) về chủ đề: chúng ta không biết tại sao nó khó, không phải bằng bất kỳ bằng chứng nào, và các phương pháp tốt nhất mà chúng ta đã chạy trong thời gian đa thức (nhưng cũng ít hơn đáng kể thời gian theo hàm mũ). Kết quả là primality testing là ngay cả trong P là khá gần đây; xem trang Wikipedia được liên kết.

Giải thích phỏng đoán tốt nhất mà tôi biết về độ khó là các số nguyên tố được phân phối ngẫu nhiên. Một trong những kết quả dễ hiểu là Dirichlet's theorem. Định lý này nói rằng mọi tiến trình số học chứa vô số các số nguyên tố, nói cách khác, bạn có thể nghĩ các số nguyên tố dày đặc liên quan đến sự tiến triển, có nghĩa là bạn không thể tránh chạy vào chúng.Đây là bộ sưu tập khá đơn giản của các kết quả như vậy; trong tất cả chúng, các số nguyên tố xuất hiện theo nhiều cách tương tự với các số ngẫu nhiên.

Sự khó khăn của việc bao thanh toán như vậy là tương tự như không thể đảo ngược một miếng đệm một lần. Trong một pad thời gian, có một chút chúng tôi không biết XOR với một số khác chúng tôi không. Chúng tôi nhận được không thông tin về một chút cá nhân biết kết quả của XOR. Thay thế "bit" bằng "prime" và phép nhân với XOR, và bạn có vấn đề bao thanh toán. Nó giống như bạn đã nhân hai số ngẫu nhiên với nhau và bạn nhận được rất ít thông tin từ sản phẩm (thay vì thông tin bằng 0).