Tôi biết rằng kiểm tra tính nguyên tố của Miller–Rabin sẽ yêu cầu tính nguyên tố cho một số tổng hợp với nhất một $\frac{1}{4}$ xác suất cho một số hỗn hợp lẻ, tùy ý $n$ và một nhân chứng ngẫu nhiên $a$ được chọn đều trong khoảng $[2,n-1)$. cái gì thật sự cơ hội trung bình mà bài kiểm tra tuyên bố sai rằng số đó là số nguyên tố? Làm thế nào để cơ hội thay đổi như kích thước của $n$ đi lên? Cơ hội thay đổi như thế nào nếu $n$ không chia hết cho bất kỳ số nguyên tố nhỏ nào cho đến 2000?
tôi hỏi vì tờ giấy này mô tả xác suất mà một hỗn hợp sẽ sống sót sau một số vòng kiểm tra. xác suất là $p_{k,t}$ với $k$ là kích thước của số được kiểm tra theo bit và $t$ là số vòng được chạy. Bài báo chứng minh rằng $\forall k \ge 2:p_{k,1} \le k^2 4^{2-\sqrt{k}}$, nhưng bất đẳng thức này chỉ là một giới hạn trên và tồn tại một bằng chứng riêng cho thấy giới hạn mạnh hơn nhiều $p_{600,1} \le 2^{-75}$. Tôi muốn tìm một hàm có giới hạn trên mạnh cho $p_{k,t,n}$ với $n$ là phép chia thử cho tất cả các số nguyên tố nhỏ hơn $n$, nhưng tôi không hiểu rõ toán học đằng sau bài báo này đủ để nghĩ ra điều đó.
Bảng 2 trong bài báo cung cấp một số ví dụ về giới hạn dưới cho $-\lg{p_{k,t}}$:
\begin{array}{c|ccccccccc}
k/t&1&2&3&4&5&6&7&8&9&10\ \hline
100&5&14&20&25&29&33&36&39&41&44\
150&8&20&28&34&39&43&47&51&54&57\
200&11&25&34&41&47&52&57&61&65&69\
250&14&29&39&47&54&60&65&70&75&79\
300&19&33&44&53&60&67&73&78&83&88\
350&28&38&48&58&66&73&80&86&91&97\
400&37&46&55&63&72&80&87&93&99&105\
450&46&54&62&70&78&85&93&100&106&112\
500&56&63&70&78&85&92&99&106&113&119\
550&65&72&79&86&93&100&107&113&119&126\
600&75&82&88&95&102&108&115&121&127&133
\end{mảng}
Việc tạo khóa của OpenSSL dường như giả định rằng đây không phải là trường hợp, vì nó làm tăng số vòng cho các số nguyên tố lớn hơn dưới ảo tưởng rằng tỷ lệ dương tính giả bằng cách nào đó ảnh hưởng đến tính bảo mật của số nguyên tố được tạo. Lưu ý rằng mã này được sử dụng trong thủ thế hệ thông thường, vì vậy các số nguyên tố ứng cử viên được đảm bảo phân phối đồng đều và không phải chịu tỷ lệ dương tính giả trong trường hợp xấu nhất.
Từ tiền điện tử/bn/bn_prime.c:87:
/*
* Sử dụng tối thiểu 64 vòng Miller-Rabin, sẽ cho kết quả sai
* tỷ lệ dương là 2^-128. Nếu kích thước của số nguyên tố lớn hơn 2048
* người dùng có thể muốn mức bảo mật cao hơn 128, vì vậy hãy chuyển đổi
* đến 128 vòng cho tỷ lệ dương tính giả là 2^-256.
* Trả về số vòng.
*/
tĩnh int bn_mr_min_checks(int bit)
{
nếu (bit > 2048)
trả lại 128;
trả về 64;
}
