Số lượng số nguyên lẻ mà chúng ta phải kiểm tra cho đến khi tìm được một số nguyên tố cho bất kỳ kích thước mô đun RSA tùy ý nào

Kích thước mô-đun RSA phổ biến là $1024$, $2048$, $3072$ và $4092$ chút. Trung bình chúng ta phải kiểm tra bao nhiêu số nguyên lẻ ngẫu nhiên cho đến khi chúng ta mong tìm được một số nguyên tố? Tôi biết đại khái mỗi $\ln p$ số nguyên có một số nguyên tố. Cho một $1024$ chút $p$, $\ln p = 710$. Trung bình, cần kiểm tra khoảng $710/2=355$ số lẻ trước khi tìm số nguyên tố. Có đúng không và chúng ta có thể trích xuất công thức không $(\lnp)/2$ đối với bất kỳ kích thước mô-đun RSA tùy ý nào?

Đối với RSA n-bit, bạn cần tìm hai số nguyên tố có tích là một số n-bit, mỗi số có khoảng n/2 bit. Trên thực tế, một số nhỏ hơn một chút và một số lớn hơn một chút, bởi vì bạn không muốn các số nguyên tố quá gần nhau.

Khoảng một trong ln M số xung quanh M là số nguyên tố; đó là logarit tự nhiên. ln(2) gần bằng 0,7. Nếu M = 2^(n/2) thì ln M â 0,35n. Bạn chỉ đang kiểm tra các số nguyên lẻ có khả năng là số nguyên tố gấp đôi, với xác suất 2/0,35n. Kiểm tra 0,175n số nguyên lẻ tìm số nguyên tố. Bạn cần hai, vì vậy khoảng 0,35n.

Nhưng lưu ý rằng nhiều trong số đó có ước số nhỏ và có thể được xác định rất nhanh; ví dụ: bằng cách sử dụng sàng loại bỏ các số có thừa số < 1000 hoặc 10.000. Để chấp nhận một số nguyên tố, bạn sẽ chạy thử nghiệm Miller-Rabin 50 hoặc 100 lần, trong khi 3/4 số không phải số nguyên tố bạn chạy nó một lần, 3/4 số còn lại bạn chạy nó hai lần, v.v. kiểm tra một số nguyên tố không phải là số nguyên tố thường khá nhanh.Kiểm tra hai số nguyên tố thực tế mất nhiều thời gian. Số lượng vật liệu tổng hợp mà bạn kiểm tra tính nguyên thủy không quan trọng lắm.

Tái bút: Tôi mới nhận ra rằng mọi người đang đánh giá quá cao hệ số 2. Giả sử tôi quyết định muốn có một số nguyên tố gần K lẻ nào đó, vì vậy tôi kiểm tra K, K+2, K+4, v.v. cho đến khi tôi gặp một số nguyên tố. Đặt p là số nguyên tố lớn nhất nhỏ hơn K và q là số nguyên tố đầu tiên >= K. Số lượng các số bị loại để kiểm tra không phải là khoảng cách q-p, chia cho 2 (vì chúng tôi chỉ kiểm tra các số lẻ) mà là một nửa số đó, bởi vì K có thể ở bất cứ đâu trong khoảng trống đó.

PPS Tôi vừa nhận ra rằng có điều gì đó không ổn với lập luận đó...

Không, bạn đã sai, bởi vì

Tôi biết gần như mọi số nguyên ln p đều có một số nguyên tố.

là một ước tính sơ bộ, mà thực sự là sai.

Ước tính của hàm đếm nguyên tố $\Pi(p)=p /ln(p)$ ước tính tổng số nguyên tố giữa 0 và $p$. Vì vậy, đối với một số có x bit, bạn cần xem $\Pi(2^{x}) - \Pi(2^{x-1})$ và so sánh nó với tổng số ứng cử viên, đó là $2^{x-2}$, khi bạn chỉ xem xét các số lẻ.

Bạn không ở đâu xa và sự khác biệt là nhỏ đối với số lượng lớn, nhưng công thức không đơn giản như vậy.