Нахождение больших коварных простых чисел

Проблема с использованием выражения Черника $(6к+1)(12к+1)(18к+1)$ и его обобщение состоит в том, что число всегда сравнимо с 1 по модулю 3, так что удвоенное число плюс один делится на и, следовательно, не является простым. Однако не все потеряно, и методы Ло и Нибур «Новый алгоритм построения больших чисел Кармайкла». (который вдохновил знаменитого Алфорд, Гранвиль и Померанс «Существует бесконечно много чисел Кармайкла» результат) можно использовать для получения больших чисел Кармайкла, равных 2 по модулю 3 и имеющих много множителей (что делает их подходящими для вашего коварного приложения).

Беря пример с алгоритма C Лоха и Нибура (стр. 285), мы добавляем небольшие дополнительные условия:

1. Выберите произведение простых степеней $\Lambda\leftarrow 2^{h_1}q_2^{h_2}\cdots q_r^{h_r}$ где $h_i$ все положительные и ни один из $q_i$ равно 3. (Конструкция работает лучше всего, если $q_i$ являются маленькими простыми числами, поэтому принимая $q_2=5$, $q_3=7$ и так далее - хороший выбор).
2. Протестировать все $p(\alpha_1,\ldots,\alpha_r)\leftarrow 2^{\alpha_1}q_2^{\alpha_2}\cdots q_r^{\alpha_r}+1$ с $0\le \alpha_i\le h_i$ для первобытности. Сбор успешных значений в набор $\mathcal S$ (опуская $\лямбда+1$). Вы можете опустить простое число 3 в случае, если предполагаемое простое число, делящееся на 3, немного очевидно, или потому что это вероятный выбор в качестве основы для теста Ферма.
3. Вычислить $\prod_{p\in\mathcal S}\pmod\Lambda$ и назовем этот остаток $s$.
4. Тестовые подмножества $\mathcal T\подмножество\mathcal S$ чья мощность имеет разную четность с $\mathcal S$ пока не найдем такое подмножество, что $\prod_{p\in\mathcal T}p\equiv s\pmod\Lambda$
5. Установлен $N=\prod_{p\in\mathcal S\обратная косая черта\mathcal T}p$. Это будет число Кармайкла, у него будет нечетное число простых множителей и оно будет конгруэнтно 2 по модулю 3.

Должно быть достаточно разнообразия в выборе $\mathcal Т$ чтобы получить число Кармайкла соответствующего размера. Затем вы можете умножить на два и добавить один. Так как полученное число равно $3\pmod\лямбда$, оно не будет делиться ни на одно простое делящее $\лямбда$ и имеет гораздо больше шансов стать премьер-министром (что приятно).