Câu hỏi ngẫu nhiên từ SQuAD:

Khi nào người ta phát hiện ra rằng các số nguyên tố có thể được áp dụng để tạo ra các thuật toán mật mã khóa công khai?

Bài giải:

những năm 1970

Các câu đã lấy:

1. Tuy nhiên, tầm nhìn này đã bị tan vỡ vào những năm 1970, khi nó được công bố công khai rằng số nguyên tố có thể được sử dụng làm cơ sở cho việc tạo ra các thuật toán mật mã hóa khóa công khai.
2. Số nguyên tố được sử dụng trong một số quy trình trong công nghệ thông tin, chẳng hạn như mật mã khóa công khai, sử dụng các đặc tính như khó tính các số lớn thành thừa số nguyên tố của chúng.
3. Các thuật toán hiệu quả hơn nhiều so với phép phân chia thử nghiệm đã được đưa ra để kiểm tra tính nguyên thủy của các số lượng lớn.
4. Một số thuật toán mật mã khóa công khai, chẳng hạn như RSA và trao đổi khóa Diffie-Hellman, dựa trên các số nguyên tố lớn (ví dụ: số nguyên tố 512 bit thường được sử dụng cho RSA và số nguyên tố 1024 bit là điển hình cho Diffie – Hellman.) .
5. Số nguyên tố cũng được sử dụng cho bảng băm và trình tạo số giả ngẫu nhiên.
6. Một số số nguyên tố này đã được tìm thấy bằng cách sử dụng máy tính phân tán.
7. Trong một thời gian dài, lý thuyết số nói chung và nghiên cứu về số nguyên tố nói riêng, được xem như là ví dụ điển hình của toán học thuần túy, không có ứng dụng nào ngoài mục đích tự nghiên cứu chủ đề ngoại trừ việc sử dụng số nguyên tố. răng bánh răng để phân bố độ mòn đều.
8. Các thuật toán xác định cung cấp một cách để biết chắc chắn một số đã cho có phải là số nguyên tố hay không.
9. Cụm từ "tất cả các thuật toán khả thi" không chỉ bao gồm các thuật toán được biết đến ngày nay mà còn bất kỳ thuật toán nào có thể được khám phá trong tương lai.
10. Ví dụ, phép chia thử là một thuật toán xác định bởi vì, nếu được thực hiện đúng, nó sẽ luôn xác định một số nguyên tố là số nguyên tố và một số tổng hợp là hợp số.
11. Được coi như một vấn đề quyết định, nó là vấn đề quyết định xem đầu vào có hệ số nhỏ hơn k hay không. Không có thuật toán phân tích nhân tử số nguyên hiệu quả nào được biết đến và thực tế này là cơ sở của một số hệ thống mật mã hiện đại, chẳng hạn như thuật toán RSA.
12. Trước khi bắt đầu nghiên cứu thực tế về độ phức tạp của các vấn đề thuật toán, nhiều nhà nghiên cứu đã đặt ra nhiều nền tảng.
13. Nguyên tắc cục bộ-toàn cục này một lần nữa nhấn mạnh tầm quan trọng của số nguyên tố đối với lý thuyết số.
14. Các thuật toán xác suất thường nhanh hơn, nhưng không hoàn toàn chứng minh rằng một số là số nguyên tố.
15. Tuy nhiên, thuật toán lượng tử được biết đến nhiều nhất cho vấn đề này, thuật toán Shor, chạy trong thời gian đa thức.
16. Sieve of Eratosthenes, được quy cho Eratosthenes, là một phương pháp đơn giản để tính toán các số nguyên tố, mặc dù các số nguyên tố lớn được tìm thấy ngày nay trên máy tính không được tạo ra theo cách này.
17. Một vấn đề được coi là vốn đã khó nếu giải pháp của nó đòi hỏi nguồn lực đáng kể, bất kể thuật toán được sử dụng.
18. Các thuật toán sử dụng các bit ngẫu nhiên được gọi là thuật toán ngẫu nhiên.
19. Người ta tin rằng nếu một vấn đề có thể được giải quyết bằng một thuật toán, thì sẽ tồn tại một máy Turing có thể giải quyết vấn đề đó.
20. Tuy nhiên, số Carmichael hiếm hơn đáng kể so với số nguyên tố, do đó, thử nghiệm này có thể hữu ích cho các mục đích thực tế.
21. Ví dụ, danh sách các số nguyên tố của Derrick Norman Lehmer lên tới 10,006,721, được tái bản vào cuối năm 1956, bắt đầu với 1 là số nguyên tố đầu tiên của nó.
22. Luận điểm của Cobham nói rằng một vấn đề có thể được giải quyết với một lượng tài nguyên khả thi nếu nó thừa nhận một thuật toán thời gian đa thức.
23. Euclid cũng chỉ ra cách xây dựng một số hoàn hảo từ một số nguyên tố Mersenne.
24. Tính đến tháng 1 năm 2016 [cập nhật], số nguyên tố lớn nhất đã biết có 22.338.618 chữ số thập phân.
25. Những câu hỏi như vậy đã thúc đẩy sự phát triển của nhiều nhánh khác nhau của lý thuyết số, tập trung vào các khía cạnh giải tích hoặc đại số của các con số.