Tìm các số nguyên tố quanh co lớn

Vấn đề với việc sử dụng biểu thức của Chernick $(6k+1)(12k+1)(18k+1)$ và khái quát hóa của nó là số luôn đồng dư với 1 mod 3 sao cho hai lần số cộng với một thì chia hết cho và do đó không phải là số nguyên tố. Tuy nhiên, tất cả không bị mất và các phương pháp Loh và Niebur "Một thuật toán mới để xây dựng các số Carmichael lớn" (đã truyền cảm hứng cho câu chuyện nổi tiếng Alford, Granville và Pomerance "Có vô số số Carmichael" kết quả) có thể được sử dụng để tạo ra các số Carmichael lớn là 2 mod 3 và có nhiều yếu tố (làm cho chúng phù hợp với ứng dụng quanh co của bạn).

Lấy gợi ý từ Thuật toán C của Loh và Niebur (trang 285), chúng tôi thêm các điều kiện bổ sung nhỏ:

1. Chọn một sản phẩm của quyền hạn chính $\Lambda\leftarrow 2^{h_1}q_2^{h_2}\cdots q_r^{h_r}$ ở đâu $h_i$ tất cả đều tích cực và không ai trong số $q_i$ là 3. (Việc xây dựng hoạt động tốt nhất nếu $q_i$ là các số nguyên tố nhỏ nên lấy $q_2=5$, $q_3=7$ và như vậy là một lựa chọn tốt).
2. kiểm tra tất cả $p(\alpha_1,\ldots,\alpha_r)\leftarrow 2^{\alpha_1}q_2^{\alpha_2}\cdots q_r^{\alpha_r}+1$ với $0\le \alpha_i\le h_i$ cho nguyên thủy. Thu thập các giá trị thành công vào một tập hợp $\mathcal S$ (bỏ qua $\Lambda+1$). Bạn có thể muốn bỏ qua số nguyên tố 3 trong trường hợp có một số nguyên tố giả định chia hết cho 3 là hơi rõ ràng hoặc vì đó có thể là lựa chọn cơ sở cho phép thử Fermat.
3. tính toán $\prod_{p\in\mathcal S}\pmod\Lambda$ và gọi dư lượng này $s$.
4. tập con kiểm tra $\mathcal T\subset\mathcal S$ có cardinality có tính chẵn lẻ khác với $\mathcal S$ cho đến khi tìm được tập con sao cho $\prod_{p\in\mathcal T}p\equiv s\pmod\Lambda$
5. Bộ $N=\prod_{p\in\mathcal S\dấu gạch chéo ngược\mathcal T}p$. Đây sẽ là một số Carmichael, nó sẽ có số thừa số nguyên tố là số lẻ và sẽ đồng dạng với 2 mod 3.

Nên có đủ sự đa dạng trong các lựa chọn của $\mathcal T$ để có được một số Carmichael có kích thước phù hợp. Sau đó, bạn có thể nhân hai và thêm một. Vì số kết quả là đồng dạng với $3\pmod\Lambda$, nó sẽ không chia hết cho bất kỳ phép chia nguyên tố nào $\Lambda$ và có cơ hội trở thành thủ tướng cao hơn nhiều so với mức trung bình (điều này thật tuyệt).