Bằng cách nào biết được các thừa số nguyên tố của một số nguyên nào đó?
Câu hỏi này có vẻ rất giống với câu hỏi làm thế nào để biết một số có phải là số nguyên tố hay không. Cho nên có lẽ việc giải bài toán thứ hai này là tương tự. Không đúng như thế, vì hiện nay người ta không biết phân tích một số nào đó thành tích của các thừa số nguyên tố như thế nào. Dĩ nhiên, người ta vẫn có thể cố chia cho 2, cho 3, v.v..., cho đến khi hết các số chia khả dĩ. Trên thực tế, phương pháp này chỉ được khai thác đối với những số nhỏ. Tính phức tạp của bài toán giống như phương pháp ghi mật mã RSA (chữ đầu tiên ghép của ba nhà phát minh ra nó là Rivest, Shamir và Adleman) phổ biến nhất hiện nay, là phương pháp khai thác khó khăn này để đảm bảo không bị xâm phạm. Nếu ta lấy hai số nguyên tố rất lớn, p và q, và nhân chúng với nhau để thu được số n, thì về nguyên tắc, không ai có thể đi từ n để tìm ra hai thừa số nguyên tố của nó. Một người gửi muốn gửi một bản tin mật cho một người nhận nào đó khi ấy sẽ làm như sau: anh ta mã hoá bản tin từ “khóa” là số n; khóa này không cần phải bí mật, vì dù sao đi nữa, chỉ có người nhận bản tin biết các thừa số p và q của n, từ đó có thể giả mã được. Vì vậy, phương pháp ghi mật mã này có ưu thế vô song là ''khóa công khai'': người gửi và người nhận không cần phải nhất trí với nhau từ trước về một khóa phải giữ bí mật (một việc tế nhị để đi đến kết quả cuối cùng một cách tin cậy). Dĩ nhiên, cũng không loại trừ là có người một ngày nào đó tìm ra một phương pháp để nhân tử hóa nhanh chóng các số lớn và có thể là một sự kiện lớn.
Tuy nhiên, giả thuyết này, từng là cơ sở cho một cuốn phim của Phil Robinson, Các chuyên gia, có lẽ không có tính chất thời sự. Vì sự gia tăng hiệu suất tính toán của máy tính cũng quan trọng là có thể “tạo ra” các số nguyên tố rất lớn, có hàng trăm số, cái được mất chiến lược và kinh tế thật sự trong xã hội thông tin của chúng ta.
Bảng 2. Các số ngẫu nhiên
Vào năm 1955, Stanislaw Ulam, khi ấy ở Trường Đại học Nam California, đã có ý định thay đổi sàng Eratosthenes bằng cách đếm những số còn lại mà không xét các số đã bị gạch bỏ. Sàng bắt đầu cũng giống như ở Eratosthenes, là bỏ đi tất cả các bội số của 2 (nhưng vẫn để giá trị 1):
1 3 5 7 9 11 13 15 17 19
Không kể 1, số thứ hai chưa bị gạch bỏ là 3. Người ta liền loại bỏ một số trên ba trong những số còn lại trong danh mục.
Như vậy còn lại các số sau:
1 3 7 9 13 15 19
Số thứ ba còn lại là 7. Người ta lại loại bỏ một số trên bảy, nên trong danh mục chỉ có liên quan với số 19 (ở vị trí thứ bày ở trên):
1 3 7 9 13 15
Như vậy, những số thu được, mà người ta có thể chứng minh chúng có số lượng vô hạn, được biết dưới tên là “số ngẫu nhiên”.
Việc nghiên cứu chúng có lẽ cũng khó như so với số nguyên tố.
Đặc biệt là, sự tương đương của “phỏng đoán Goldbach” đối với những số này cũng là một vấn đề mở; các phép thử tin học đã cho thấy nó đúng cho tới 100.000.
Sự giống nhau giữa các số nguyên tố và số ngẫu nhiên đến mức Martin Gardner đã cho rằng dù sao sàng Eratosthenes có thể chứa đựng nhiều thông tin hơn về tính chất của các số nguyên tố hơn là định nghĩa số học thông dụng của chúng!
