Bao nhiêu công việc để tìm $n$ như vậy?

Để cho $W$ là ngẫu nhiên $200$ số bit. Cần bao nhiêu công việc để tìm một nửa nguyên tố $n=p_1\cdot p_2$ như vậy mà $p_1,p_2 > 2^{50} $ và $|W-n|<2^{12}$?

Tổng quát hơn, hãy để $W_b$ là một số nguyên ngẫu nhiên với $b$ chút ít. Cần bao nhiêu công việc để tìm một nửa nguyên tố $n=p_1\cdot p_2$ như vậy mà $p_1,p_2 > \sqrt[4]{W_b} $ và $|W_b-n|<\sqrt[8]{W_b}$?

Phương pháp tốt nhất để tìm những con số như vậy mà tôi biết là Thuật toán 3 từ bài báo của Marc Joye Mô-đun RSA với một phần được xác định trước: Kỹ thuật và ứng dụng. Trong trường hợp này, lấy $n=200$, $n_0=150$ và $\kappa'=188$. Các yêu cầu ban đầu của vấn đề rất linh hoạt và rất có thể có các giá trị 200 bit của $W$ mà không có bán nguyên tố nào phù hợp tồn tại trong khoảng đó.Cuộc điều tra của Joye chỉ kiểm tra độ phức tạp của phương pháp theo cách thực nghiệm. Tôi sẽ đọc và cố gắng đưa ra một heuristic.

Thật đơn giản để mô tả và phân tích theo kinh nghiệm phương pháp "văn hóa dân gian" để chọn 50-bit $p$, cài đặt $q_0=\lceil W/p\rceil$ và thử nghiệm $q_0$ cho nguyên thủy. Nó sẽ mất khoảng 105 sự lựa chọn khác nhau của $p$ để tìm một số nguyên tố $q$ của 150-bit. Đối với cặp này, 150 bit hàng đầu sẽ khớp $W$ và với xác suất xung quanh $2^{-38}$ 188 bit trên cùng sẽ khớp. Điều này mang lại ngân sách công việc tổng thể là 44-45 bit cho các bài kiểm tra tính nguyên tố. Phương pháp của Joye chắc chắn sẽ cải thiện điều này, nhưng phân tích sẽ dài hơn.

Đối với câu hỏi chung với $q\approx\root 4\của n$ và độ dài khoảng $\root 8\của n$, chúng tôi mong đợi xung quanh $\frac14\root 8\của n\log n$ kiểm tra tính nguyên tố của các số xung quanh $\root 4\của n$ về kích thước đối với phương pháp dân gian, nhưng một lần nữa Joye nên cải thiện điều này.

Nếu bạn sử dụng các chức năng bao thanh toán hiện có, điều này có thể được giải quyết trong vài phút cho các số ngẫu nhiên 200 bit. Các chức năng bao thanh toán từ Pari/GP chẳng hạn.

Thuật toán dưới đây không chỉ bao thanh toán các số liên tiếp. Xem bên dưới.

Đây là thuật toán chung đã được chuyển đổi thành một thuật toán hoạt động chương trình:

Tạo W, một số 200 bit ngẫu nhiên

sànglimit = 250 giới hạn nguyên tố = 2000000

precompute pr = tích của các số nguyên tố primelimit đầu tiên

Với n1 = W+1 đến W+giới hạn sàng

Nếu n1 có dạng 6k+1 hoặc 6k+5

 nếu gcd(n1,pr) là 1

   f = thừa số(n1)

      nếu số thừa số của n1 là 2 và cả hai đều >2^50   
          in Lời giải f  

Vòng

Dòng:

nếu gcd(n1,pr) là 1

là một cách nhanh chóng để bỏ qua các số có thừa số nguyên tố nhỏ hơn số nguyên tố thứ 2 triệu.

Bước tính toán trước pr được tối ưu hóa trong Pari/GP và chỉ mất 7,785 giây trên phần cứng chậm.

Đối với trường hợp xấu nhất là số 200 bit, hàm thừa số trong Pari/GP sử dụng phương pháp MPQS và mất ít hơn 30 giây trên phần cứng cũ.

Đây là một số 200 bit ngẫu nhiên W: 1567470448908230034126591070540826459978233372650796513704199

Chương trình chỉ nhân tử một số W+10 và tìm ra nghiệm

p1 = 5346955435967300929
p2 = 293151956787285973328498761492202409914321  

p1 là 63 bit, p2 là 138 bit, n = p1*p2

|W-n| = 10, |W-n|< 2^12